BOJ 17129 - 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 (Python)

S1, BFS

문제

윌리암슨수액빨이딱따구리 세 식구가 정보섬에 올라왔다!

세 윌리암슨수액빨이딱따구리는 정보섬 2층 어딘가에 모여 앉아 쉬고 있었는데, 저 멀리 청국장과 스시와 맥앤치즈가 있는 것을 발견했다! 아빠는 청국장, 엄마는 스시, 아이는 맥앤치즈가 먹고 싶다. 그래서 이 셋은 현위치로부터 가장 가까운 음식을 먹으러 가기로 했다.

정보섬 2층은 An×m의 격자로 표현된다. 어떤 Ai,j가 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다. 윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다. 윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있다. 2, 3, 4, 5는 장애물이 아니므로 지나갈 수 있다. 격자 밖으로는 나갈 수 없으며 시작점으로부터 시작점까지의 거리는 0이다. 시작점은 윌리암슨수액빨리딱따구리의 위치, 즉 2의 위치이다.

과연 윌리암슨수액빨이딱따구리 식구는 어떤 음식에 더 빨리 도착할 수 있을까?

풀이

• 아마도 2 → 3, 2 → 4, 2 → 5를 각각 따로 찾아서 최솟값을 구하면
  시간초과가 발생했을 것이다.
• 제한 사항이 (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106)이기 때문에, 한 번의 탐색으로 최솟값을 찾아야했다.
• 이후에는 간단한 bfs

from sys import stdin
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 2 -> 3, 4, 5 중 가장 빠른 거 찾기

n, m = map(int, stdin.readline().split())
graph = [[] for _ in range(n)]
for i in range(n):
    graph[i] = list(map(int, stdin.readline().rstrip()))

visited = [[0] * m for _ in range(n)]
res = int(1e9)

def bfs(sx, sy):
    global res
    q = deque()
    q.append([sx, sy, 0])
    visited[sx][sy] = 1
    
    while q:
        x, y, cnt = q.popleft()
        
        if graph[x][y] in [3, 4, 5]:
            res = min(res, cnt)
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<n and 0<=ny<m and graph[nx][ny] != 1 and not visited[nx][ny]:
                visited[nx][ny] = 1
                q.append([nx, ny, cnt + 1])

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            bfs(i, j)

if res != int(1e9):
    print("TAK")
    print(res)
else:
    print("NIE")