greentea31's Note

https://leetcode.com/problems/design-circular-queue/

풀이 과정

원형 큐를 구현하는 문제이다.

선형 큐를 직접 구현시 front, rear 변수를 두고 구현했었는데 이는 큐의 사이즈 만큼 push()가 이루어지면 pop으로 큐를 다 비워도 추가로 원소를 넣을 수 없는 문제점이 있었다. 그래서 front, rear 변수가 큐의 크기를 넘어가면 큐의 크기로 나눈 나머지 값을 사용하게 해서 이미 변수가 채워졌다 없어진 공간도 다시 재활용이 가능하게 구현하였다.

소스 코드

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [None for _ in range(k)]
        self.maxlen = k
        self.front = 0
        self.rear = 0

    def enQueue(self, value: int) -> bool:
        if self.q[self.rear] is None:
            self.q[self.rear] = value
            self.rear = (self.rear + 1) % self.maxlen
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if self.q[self.front] is None:
            return False
        else:
            self.q[self.front] = None
            self.front = (self.front + 1) % self.maxlen
            return True

    def Front(self) -> int:
        return self.q[self.front] if self.q[self.front] is not None else -1

    def Rear(self) -> int:
        return self.q[self.rear - 1] if self.q[self.rear - 1] is not None else -1

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.q[self.front] is None
 
    def isFull(self) -> bool:
        return self.front == self.rear and self.q[self.front] is not None

https://leetcode.com/problems/implement-queue-using-stacks/

풀이 과정

스택을 사용해 큐를 구현하는 문제이다.

큐를 스택으로 구현하는데엔 2개의 스택이 필요하다. push때는 스택에 넣고, pop이나 맨 위의 원소를 뽑아야 할 때는 스택의 원소를 다른 스택에 모두 넣어서 스택의 원소의 순서를 모두 뒤집고 스택 탑에 접근해서 큐를 구현할 수 있다.

소스 코드

class MyQueue:
    def __init__(self):
        self.st = []
        self.st2 = []

    def push(self, x: int) -> None:
        self.st.append(x)

    def pop(self) -> int:
        self.peek()
        return self.st2.pop()

    def peek(self) -> int:
        if not self.st2:
            while self.st:
                self.st2.append(self.st.pop())
        return self.st2[-1]

    def empty(self) -> bool:
        if len(self.st) == 0 and len(self.st2) == 0:
            return True
        else:
            return False

https://leetcode.com/problems/implement-stack-using-queues/

풀이 과정

큐로 스택을 구현하는 문제이다. 큐 2개로 스택을 구현하라고 하고 있고, 후속조치로 큐 1개로 스택을 구현해달라고 하고 있다.

1. 큐 2개로 구현하기

pop 할 때 스택에서 맨 처음 나오는 값이 큐에서는 제일 마지막에서 나오는 값일 것이므로, push 받을 때는 입력받은 값을 그냥 큐에 넣어주면 된다. pop 받을 때는 큐의 길이 - 1만큼 다른 큐에 원소들을 빼고 마지막 하나 남은 값을 pop 해주면 된다. top을 받았으면 마지막 하나 남은 값을 반환해주고 다시 큐에 넣어주면 된다. 스택이 비어있는지 판단하려면 큐 2개가 전부 비어있으면 스택도 비어있는 것이고, 아니면 스택에 원소가 있는 것이다.

2. 큐 1개로 구현하기

pop할 때 스택에서 맨 처음 나오는 값이 큐에서는 제일 마지막으로 나오는 값임을 생각하며 그냥 push 받을 때 push 받은 값이 큐의 맨 앞으로 가게 조작해주면서 스택의 기능을 하게 할 수 있다. 일단 입력받은 값을 큐에 넣고 큐의 사이즈 - 1번만큼을 앞에서 빼준 다음에 다시 뒤에 붙여주면 된다.

예시)

1, 2, 3이라는 큐에서 4를 입력받으면

1, 2, 3 -> 1, 2, 3, 4 -> 2, 3, 4, 1 -> 3, 4, 1, 2 -> 4, 1, 2 3

pop()하면 4가 나올 것이고 나중에 입력받으면 먼저 나오는 스택이 구현됨.

소스 코드

큐 1개로 구현한 코드이다.

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]
        

    def empty(self) -> bool:
        return True if len(self.q) == 0 else False

https://leetcode.com/problems/daily-temperatures/

풀이 과정

각 날짜의 온도가 주어질 때, 어떤 날짜에서 며칠을 기다려야 더 따뜻한 날이 되는지 출력하는 문제이다.

2중 for문 돌려서 O(N^2)로도 해결할 수 있겠지만, 스택을 활용해서 더 효율적으로 문제를 해결할 수 있다.

수의 index를 스택에 저장하면서, 스택탑의 index 날짜의 온도보다 더 따뜻한 날의 index가 들어오면 스택을 pop하면서 따뜻한 날의 index - 스택 탑의 index를 계산해서 정답 리스트에 저장해주면 문제를 해결할 수 있다. 

소스 코드

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        answer = [0 for _ in range(len(temperatures))]
        for a, b in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < b:
                last = stack.pop()
                answer[last] = a - last
            stack.append(a)
        return answer

https://leetcode.com/problems/remove-duplicate-letters/

풀이 과정

중복된 문자를 제거하되, 문자열을 사전식 순서로 나열하는 문제이다.

문제가 약간 이해하기 어려운데 set으로 중복 문자 없애고 sort로 정렬하라는 소리인가? 싶긴 하지만 예시를 보면 그렇지 않다. 2번 예시를 보자.

"cbacdcbc"가 예시로 주어져 있는데 여기에 단순히 ''.join(sorted(set(s))) 를 하게 되면 답이 'abcd'가 나오게 된다. 하지만 이 문제에서 원하는 정답은 acdb로 중복을 제거할 때 어떤 문자를 지우는지로 사전식 순서를 맞추되 문자의 위치를 옮기지는 않는 그런 방식을 요구하고 있다. 중복된 문자를 어떤 것을 지우는지에 따라 나올수 있는 것이 ['cbad', 'bacd', 'acbd'..]의 다양한 결과가 나올 수 있는데 이 중에서 사전식 순서로 맨 앞에 나와있는 것은 'acbd'니까 이것을 출력하라는 것이다.

사전상 앞에 있는 알파벳의 index를 찾고 거기서 문자열을 분리하고, 분리한 문자열에서 중복을 제거한 것이 원래 문자열에서 중복을 제거한 것과 같으면 정답에 분리 기준 문자를 추가하고... 를 재귀식으로 반복하는 방법으로 문제를 해결할 수 있다.

소스 코드

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters(suffix.replace(char, ''))
        return ''

https://www.acmicpc.net/problem/10026

풀이 과정

격자 칸의 그림에 같은 색으로 이루어진 구역의 수를 구하되, 적록색약인 (적색과 녹색 구분 불가)사람과 적록색약이 아닌 사람이 보는 구역의 수를 각각 구하라는 문제이다.

BFS로 연결 요소의 수를 한 번 구하고, 모든 녹색을 적색으로 혹은 모든 적색을 녹색으로 바꿔서 색깔을 구분 못하게 한 뒤, BFS로 연결 요소의 수를 한 번 더 구해주면 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;
char board[101][101];
bool visit[101][101];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int N;

void bfs(int y, int x) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            
            if (0 <= ny && ny < N && 0 <= nx && nx < N) {
                if (board[ny][nx] != board[y][x]) continue;
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
            }
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    int answer = 0;
    int answer2 = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j]) continue;
            bfs(i, j);
            answer++;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visit[i][j] = false;
            if (board[i][j] == 'G') board[i][j] = 'R';
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j]) continue;
            bfs(i, j);
            answer2++;
        }
    }

    cout << answer << ' ' << answer2;

    return 0;
}

https://www.acmicpc.net/problem/1012

풀이 과정

상하좌우 배추에 배추흰지렁이가 옮겨서 해충으로 부터 보호할 수 있을 때, 격자 모양의 밭의 모든 배추를 보호하려면 배추흰지렁이가 몇 마리 필요한지 구하는 문제이다.

연결 요소의 개수를 구하라는 문제와 같다. flood-fill을 bfs로 구현하고 미방문 배추를 bfs로 방문해주면서 연결 요소의 개수를 세주면 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;
bool board[51][51];
bool visit[51][51];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int M, N, K;

void bfs(int y, int x) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];

            if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                if (!board[ny][nx]) continue;
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        cin >> M >> N >> K;
        int Y, X;
        int answer = 0;

        for (int i = 0; i < K; i++) {
            cin >> X >> Y;
            board[Y][X] = true;
        }

        for (int i = 0 ; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] && !visit[i][j]) {
                    answer++;
                    bfs(i, j);
                }
            }
        }

        cout << answer << '\n';


        for (int i = 0; i < 51; i++) {
            for (int j = 0; j < 51; j++) {
                board[i][j] = false;
                visit[i][j] = false;
            }
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/1697

풀이 과정

현재 N에 있고, 동생이 K에 있을 때, 하루마다 현재 점에서 +1, -1, *2로 이동이 가능한데, 동생을 찾는 가장 빠른 시간을 구하는 문제이다.

BFS로 +1, -1, *2 이동해보면서 원점으로 부터의 거리를 계산하고, K일때 원점에서의 거리를 출력해주면 된다. 동생이 10만까지만 위치 가능하긴 해도, 수빈이는 10만을 넘어선 점에 위치가 가능하긴 한데 이 문제에서는 10만을 넘어가면 무조건 원점과 10만까지의 거리보다 더 많은 거리를 이동해야 하므로 고려해주지 않아도 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int d[100001];

    for (int &i : d) {
        i = -1;
    }

    queue<int> Q;

    int N, K;
    cin >> N >> K;

    d[N] = 0;
    Q.push(N);

    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        if (cur == K) {
            cout << d[K];
            return 0;
        }

        for (int next : {cur-1, cur+1, 2*cur}) {
            if (next < 0 || next > 100000) continue;
            if (d[next] != -1) continue;
            d[next] = d[cur] + 1;
            Q.push(next);
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/4179

풀이 과정

벽과 지나갈 수 있는 공간, 불과 지훈이의 위치가 주어지고 불은 상하좌우로 하루마다 한칸씩 번지며, 지훈이는 하루에 한칸씩 이동이 가능할 때, 지훈이가 미로에서 탈출할 수 있는지, 탈출이 가능하다면 걸리는 최소 날짜는 몇 일인지 구하는 문제이다.

flood fill bfs 문제이다. 지훈이를 불과 벽을 피해 bfs로 이동시키면서 미로의 밖에 도착이 가능한지, 가능하다면 도착하기까지의 날짜가 얼마나 걸리는지를 구해주면 된다.

풀고나서 다른 사람의 코드를 봤더니 불에 대한 BFS를 먼저 돌리고 각 칸에서 불이 번지는 시간을 먼저 계산후 지훈이의 BFS를 구하는 방법으로 푼 코드가 많았다. 그런데 사실 BFS를 2번 돌릴 필요가 없다. BFS의 시작 시점에 큐에 지훈이의 시작 위치를 넣은 후 불의 위치를 넣어서 지훈이의 진행과정이 불의 진행과정보다 먼저 이루어지게 한 후 BFS를 한번만 돌리면 된다.

# . F

# J #

# # #

같은 경우에 IMPOSSIBLE이 나와야 올바르게 짠 코드이다. 지훈이를 먼저 진행시키는 만큼 지훈이가 모서리에 도착하자마자 탈출 성공 처리를 해버리면 탈출이 가능한 잘못된 답이 나오게 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

char board[1001][1001];
int day[1001][1001];
int R, C;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int bfs() {
    queue<pair<int, int>> Q;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'J') Q.push(make_pair(i, j));
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'F') Q.push(make_pair(i, j));
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (board[cur.first][cur.second] == 'J') {
            if (cur.first == 0 || cur.first == R-1 || cur.second == 0 || cur.second == C-1) {
                return day[cur.first][cur.second];
            }
        }

        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (0 <= ny && ny < R && 0 <= nx && nx < C) {
                if (board[cur.first][cur.second] == 'J') {
                    if (board[ny][nx] != '.') continue;
                    board[ny][nx] = 'J';
                    day[ny][nx] = day[cur.first][cur.second] + 1;
                    Q.push(make_pair(ny, nx));
                } else if (board[cur.first][cur.second] == 'F') {
                    if (board[ny][nx] == 'F' || board[ny][nx] == '#') continue;
                    board[ny][nx] = 'F';
                    Q.push(make_pair(ny, nx));
                }
            }
        }
    }

    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0 ; j < C; j++) {
            cin >> board[i][j];
        }
    }

    int answer = bfs();
    if (answer == -1) cout << "IMPOSSIBLE";
    else cout << answer+1;

    return 0;
}

https://www.acmicpc.net/problem/7576

풀이 과정

하루가 지날 때마다 근처에 있는 토마토가 익을 때, 모든 토마토가 익는데 며칠이 걸리는지 구하는 문제이다.

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

큐로 flood-fill을 구현하는 일종의 bfs 문제이다. board에 토마토가 익는데 걸리는 날짜가 저장되어 있다고 생각하고, flood-fill로 주변 토마토를 익혀가면서 주변 토마토의 board값을 기존 토마토의 board값 + 1을 시켜주면서 모든 토마토를 익힌다.

bfs 과정이 끝나면 board를 다 살펴보면서 0이 있으면 익지 않은 토마토가 존재하므로 -1, 0이 없으면 board의 최댓값의 -1을 답으로 출력해주면 된다. board값이 1로 주어진 토마토는 주어진 즉시, 0일째에 이미 익은 토마토이지만 1일째 익은 것으로 인식되므로 모든 토마토의 익은 날짜가 1씩 더해져 있기 때문 출력 전 -1을 해주는 것이다.

시작점이 여러 곳인 bfs는 그냥 bfs의 시작시에 큐에 여러 점을 넣어주고 돌리면 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

int board[1001][1001];
int M, N;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs() {
    queue<pair<int, int>> Q;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 1) Q.push(make_pair(i, j));
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = cur.second + dx[i];
            int ny = cur.first + dy[i];
            if (0 <= nx && nx < M && 0 <= ny && ny < N) {
                if (board[ny][nx] == 0) {
                    board[ny][nx] = board[cur.first][cur.second] + 1;
                    Q.push(make_pair(ny, nx));
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> M >> N;
    int num;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> num;
            board[i][j] = num;
        }
    }

    bfs();

    int answer = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 0) {
                cout << -1;
                return 0;
            }

            if (board[i][j] > answer) {
                answer = board[i][j];
            }
        }
    }

    cout << answer-1;

    return 0;
}