[Python/파이썬] 백준 17129번 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

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

코드

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

n, m = map(int, input().split())
map_data = [input() for _ in range(n)]

for i in range(n):
    for j in range(m):
        if map_data[i][j] == "2":
            start = [i, j]
            break

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

q = deque([[*start, 0]])
visited = [[False]*m for _ in range(n)]
visited[start[0]][start[1]] = True
while q:
    x, y, d = q.popleft()
    if map_data[x][y] in ["3", "4", "5"]:
        print("TAK\n{}".format(d))
        exit()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and map_data[nx][ny] != "1":
            q.append([nx, ny, d+1])
            visited[nx][ny] = True
print("NIE")

 

격자 모양의 칸을 탐색해야 하는 문제이고, 각 칸을 이동하는데 걸리는 시간이 동일하기 때문에 BFS를 사용하여 풀었다. 윌리암어쩌구가 있는 곳("2")부터 "3" 또는 "4" 또는 "5" 중 하나가 나올 때까지 탐색하면 된다. 만약 갈 수 있는 모든 칸을 탐색하더라도 3, 4, 5 중 어느 것도 찾지 못한다면 "NIE"를 출력하면 된다.

 

N과 M의 범위가 워낙 커서 Python으로는 시간 초과가 발생하고, PyPy3로만 통과가 된다.