317. 백조의 호수

백준

1. Python

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

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def check():
    while q:
        x, y = q.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 < n and 0 <= ny < m:
                if not c[nx][ny]:
                    if lake[nx][ny] == '.':
                        q.append([nx, ny])
                    else:
                        q_temp.append([nx, ny])
                    c[nx][ny] = 1
    return False

def melt():
    while wq:
        x, y = wq.popleft()
        if lake[x][y] == 'X':
            lake[x][y] = '.'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not wc[nx][ny]:
                    if lake[nx][ny] == 'X': #. 다음 칸이 빙판이면 다음번 bfs 때 물이 되기 때문에 바로 녹이지 않고 임시큐에 넣는다
                        wq_temp.append([nx, ny])
                    else:
                        wq.append([nx, ny])
                    wc[nx][ny] = 1


n, m = map(int, input().split())
c = [[0] * m for _ in range(n)]
wc = [[0] * m for _ in range(n)]

lake, swan = [], []
q, q_temp, wq, wq_temp = deque(), deque(), deque(), deque()

for i in range(n):
    row = list(input().rstrip())
    lake.append(row)
    for j, k in enumerate(row):
        if lake[i][j] == 'L':
            swan.extend([i, j])
            wq.append([i, j])
        elif lake[i][j] == '.':
            wc[i][j] = 1
            wq.append([i, j])

x1, y1, x2, y2 = swan
q.append([x1, y1])
lake[x1][y1], lake[x2][y2], c[x1][y1] = '.', '.', 1 #백조에 해당하는 칸도 물에 대한 큐에 넣어준다.
cnt = 0

while True:
    melt()
    if check():
        print(cnt)
        break
    q, wq = q_temp, wq_temp
    q_temp, wq_temp = deque(), deque()
    cnt += 1