[백준] 2178 : 미로 탐색 python

 

BFS를 수행하면서 각 위치마다 거리를 적어두는 식으로 해결하면 되는 문제다.

 

from collections import deque
n,m = map(int,input().split())

graph = [[]for i in range(n)]

for i in range(n):
    data = input()
    for c in data[:]:
        graph[i].append(int(c))
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if graph[nx][ny]==0:
                continue
            if graph[nx][ny]==1:
                graph[nx][ny] = graph[x][y]+1
                queue.append((nx,ny))
    return graph[n-1][m-1]

print(bfs(0,0))