BOJ 3197 · 백조의 호수

알고리즘 분류 : BFS  

두 마리의 백조가 서로 만나는 데 걸리는 시간을 구하는 문제다. 백조는 빙판을 지날 수 없으며, 물로만 이동이 가능하다. 또한, 매일 물과 인접한 빙판이 녹아서 물로 변한다.

입력으로 주어지는 맵의 범위가 최대 1500*1500이므로, 일반적인 BFS 방법으로는 시간 초과가 나온다. 여러 방법이 있겠지만, 아래 코드에서는 큐(Queue) 4개를 이용하는 방법을 사용했다.

• 빙판이 물로 녹는 BFS와, 백조가 이동하는 BFS를 따로 나눈다.
• 물을 위한 큐는 wq1, wq2가 있고, 백조를 위한 큐는 sq1, sq2가 있다.
• 입력으로 주어지는 호수 맵에서 물('.')의 좌표를 wq1에 모두 넣는다.
• 호수 맵에서 백조('L')의 좌표를 sq1에 하나 넣고, 다른 하나의 백조 위치는 도착 위치(ex, ey)로 저장한다.

• 우선, 빙판을 먼저 녹이고, 백조를 이동시켜야 한다.
• 물 BFS에서 맵을 이동하면서, 빙판('X')을 물('.')로 녹인다.
• 다음 위치가 물('.')인 경우, sq1에 좌표를 넣는다.
• 다음 위치가 빙판('X')인 경우, sq2에 좌표를 넣는다.

• 백조 BFS에서 맵을 이동하면서, 도착 위치에 있는 백조를 만날 수 있는지 확인한다.
• 다음 위치가 물('.')인 경우, wq1에 좌표를 넣는다.
• 다음 위치가 빙판('X')인 경우, wq2에 좌표를 넣는다.

• 현재 wq2에는 빙판의 위치가 들어있다. 다음 이동을 위해 wq1를 wq2로 대체한다.
• 현재 sq2에는 빙판의 위치가 들어있다. 다음 이동을 위해 sq1를 sq2로 대체한다.
• wq2와 sq2를 초기화한다.
• 백조가 만날 때까지, 위 과정을 반복한다.

    Day1 (초기)          Day2 (+1)         Day3 (+2)

...XXXXXX..XX.XXX  ....XXXX.......XX  .....XX.......... 
....XXXXXXXXX.XXX  .....XXXX..X.....  ......X.......... 
...XXXXXXXXXXXX..  ....XXX..XXXX....  .....X.....X..... 
..XXXXX.LXXXXXX..  ...XXX..L.XXXX...  ....X...L..XX.... 
.XXXXXX..XXXXXX..  ..XXXX....XXXX...  ...XX......XX.... 
XXXXXXX...XXXX...  ..XXXX.....XX....  ....X............ 
..XXXXX...XXX....  ....XX.....X.....  ................. 
....XXXXX.XXXL...  .....XX....X.L...  .............L... 

---

C++ 소스코드

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

int R, C, ex, ey, ans;
char a[1500][1500];
bool wc[1500][1500], sc[1500][1500];
const int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
queue<pair<int, int>> wq1, wq2, sq1, sq2;

void water() {
    while (!wq1.empty()) {
        int x = wq1.front().first, y = wq1.front().second; wq1.pop();
        a[x][y] = '.';
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C || wc[nx][ny]) continue;
            if (a[nx][ny] == '.') wq1.push(make_pair(nx, ny));
            else wq2.push(make_pair(nx, ny));
            wc[nx][ny] = true;
        }
    }
}

bool swan() {
    while (!sq1.empty()) {
        int x = sq1.front().first, y = sq1.front().second; sq1.pop();
        if (x == ex && y == ey) return true;
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C || sc[nx][ny]) continue;
            if (a[nx][ny] == '.') sq1.push(make_pair(nx, ny));
            else sq2.push(make_pair(nx, ny));
            sc[nx][ny] = true;
        }
    }
    return false;
}

int main() {
    scanf("%d %d", &R, &C);
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            scanf(" %1c", &a[i][j]);
            if (a[i][j] == 'L') {
                if (sq1.empty()) {
                    sq1.push(make_pair(i, j));
                    sc[i][j] = true;
                } else ex = i, ey = j;
                a[i][j] = '.';
            }
            if (a[i][j] == '.') {
                wq1.push(make_pair(i, j));
                wc[i][j] = true;
            }
        }
    }
    while (true) {
        water();
        if (swan()) break;
        wq1 = wq2;
        sq1 = sq2;
        wq2 = queue<pair<int, int>>();
        sq2 = queue<pair<int, int>>();
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}

---

PyPy3 소스코드

from collections import deque
from sys import stdin
input = stdin.readline

ex, ey, ans = 0, 0, 0
dx, dy = (0, -1, 0, 1), (-1, 0, 1, 0)
R, C = map(int, input().split())
a = [list(input().strip()) for _ in range(R)]
wc = [[False]*C for _ in range(R)]
sc = [[False]*C for _ in range(R)]
wq1, wq2 = deque(), deque()
sq1, sq2 = deque(), deque()

def water():
    while wq1:
        x, y = wq1.popleft()
        a[x][y] = '.'
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= R or ny < 0 or ny >= C or wc[nx][ny]:
                continue
            if a[nx][ny] == '.':
                wq1.append((nx, ny))
            else:
                wq2.append((nx, ny))
            wc[nx][ny] = True

def swan():
    while sq1:
        x, y = sq1.popleft()
        if x == ex and y == ey:
            return True
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= R or ny < 0 or ny >= C or sc[nx][ny]:
                continue
            if a[nx][ny] == '.':
                sq1.append((nx, ny))
            else:
                sq2.append((nx, ny))
            sc[nx][ny] = True
    return False

for i in range(R):
    for j in range(C):
        if a[i][j] == 'L':
            if not sq1:
                sq1.append((i, j))
                sc[i][j] = True
            else:
                ex, ey = i, j
            a[i][j] = '.'
        if a[i][j] == '.':
            wq1.append((i, j))
            wc[i][j] = True
while True:
    water()
    if swan():
        break
    wq1 = wq2
    sq1 = sq2
    wq2 = deque()
    sq2 = deque()
    ans += 1
print(ans)

✓ Python 3로 제출하면 시간 초과가 나와서, PyPy3로 제출했다.

---

참고

• 백준 온라인 저지 : BOJ 3197