[백준/BOJ] platinum5 - 3197번 백조의 호수 (Python)

▶3197 - 백조의 호수

백준 로고

▶문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는지 계산하는 프로그램을 작성하시오.

 

▶입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

 

▶출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

728x90

▶풀이

백조끼리 만나는 bfs와 얼음이 녹는 bfs, 두 개로 구현해 주었다.

백조끼리 만날 때, '.'면 그냥 queue에 담아주고 x면 queue_tmp에 담아주었다.

그렇게 처리한 이유는 얼음이 녹고 나면 바로 만나는 x가 다음 queue가 되기 때문에,

queue_tmp에 넣어주고 다음에 queue로 처리해 주면 된다.

 

melt도 마찬가지다.

전체적으로 queue를 4개를 만들어서 처리해 주는 방법을 사용하였다.

말로 설명한 것을 보는 것보다 코드를 보는 게 훨씬 이해하기 쉬울 것이다.

from collections import deque

def bfs():
    while queue:
        x, y = queue.popleft()

        if x == x2 and y == y2:
            return True
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c:
                if visit[nx][ny] == 0:
                    if arr[nx][ny] == '.':
                        queue.append((nx, ny))
                    else:
                        queue_tmp.append((nx, ny))
                    visit[nx][ny] = 1
    return False


def melt():
    while water:
        x, y = water.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c:
                if visit_melt[nx][ny] == 0:
                    if arr[nx][ny] == 'X':
                        water_tmp.append((nx, ny))
                        arr[nx][ny] = '.'
                    else:
                        water.append((nx, ny))
                    visit_melt[nx][ny] = 1


r, c = map(int, input().split())
arr = []
swan = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

visit = [[0 for _ in range(c)] for _ in range(r)]
visit_melt = [[0 for _ in range(c)] for _ in range(r)]
cnt = 0

queue, queue_tmp = deque(), deque()
water, water_tmp = deque(), deque()

for i in range(r):
    tmp = list(input().strip())
    arr.append(tmp)
    for j in range(len(tmp)):
        if tmp[j] == 'L':
            swan.extend([i, j])
            water.append((i, j))
        if tmp[j] == '.':
            water.append((i, j))

x1, y1, x2, y2 = swan
arr[x1][y1] = '.'
arr[x2][y2] = '.'
visit[x1][y1] = 1
queue.append((x1, y1))

while True:
    if bfs():
        print(cnt)
        break
    melt()
    water = water_tmp
    queue = queue_tmp
    water_tmp = deque()
    queue_tmp = deque()
    cnt += 1