[BOJ] 3055번 탈출 python

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

문제
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다. 티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

input 1
3 3
D.*
...
.S.

output 1
3

input 2
3 3
D.*
...
..S

output 2
KAKTUS

input 3
3 6
D...*.
.X.X..
....S.

output 3
6

input 4
5 4
.D.
....
..X.
S..
....

output 4
4

import sys
from collections import deque

def bfs():
    q = deque()
    q.append([S[0], S[1], 0])

    while q:
        x, y, cnt = q.popleft()

        if x ==  D[0] and y == D[1]:
            return cnt
        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]
            if -1 < nx < R and -1 < ny < C and not visited[nx][ny]:
                visited[nx][ny] = True
                if arr[nx][ny] == '.' and cnt + 1 < flood_visited[nx][ny] or flood_visited[nx][ny] == -1:
                    q.append([nx, ny, cnt + 1])

    return 'KAKTUS'


def flood():
    global flood_queue
    tmp = deque()

    while flood_queue:
        for pos in flood_queue:
            x, y, cnt = pos
            for t in range(4):
                nx = x + dx[t]
                ny = y + dy[t]
                if -1 < nx < R and -1 < ny < C and arr[nx][ny] in '.' and flood_visited[nx][ny] == -1:
                    flood_visited[nx][ny] = cnt + 1
                    tmp.append([nx, ny, cnt + 1])
        flood_queue = tmp
        tmp = deque()


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

input = sys.stdin.readline
R, C = map(int, input().split())
arr = [list(map(str, list(input().strip()))) for _ in range(R)]

flood_visited = [[-1] * C for _ in range(R)]
visited = [[False] * C for _ in range(R)]

flood_queue = deque()
S = [-1, -1]
D = [-1, -1]

for i in range(R):
    for j in range(C):
        if arr[i][j] == '*':
            flood_visited[i][j] = 0
            flood_queue.append([i, j, 0])
        elif arr[i][j] == 'X':
            flood_visited[i][j] = 0
        elif arr[i][j] == 'S':
            visited[i][j] = True
            S = [i, j]
        elif arr[i][j] == 'D':
            D = [i, j]

flood()
answer = bfs()
print(answer)

고려해야 할 사항이 많았을 뿐 어렵지는 않았는데, 집중을 못 했는지 돌을 고려해야 하는 것을 마지막에 알아차렸다. 물을 흘려보내서 각 칸에 물이 몇 번째에 차는지 구하고 난 뒤에 고슴도치가 이동할 수 있는 길을 구했다.