Jinho Tech

최단경로를 찾아야 되는 기본적인 BFS 문제이다.

from collections import deque

def bfs():
    queue = deque()
    queue.append((0, 0))
    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < M) and graph[Y][X] == 1:
                graph[Y][X] = graph[y][x] + 1
                queue.append((Y, X))

N, M = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(N)]
bfs()
print(graph[N-1][M-1])