2178번 미로 탐색(python3)

bfs를 적용하면 간단하게 해결되는 문제다.

기존의 bfs는 visited 배열을 설정해줄때 0은 방문하지 않은 곳, 1은 방문한 곳으로 해주었는데, 이 문제의 경우에는 방문하지 않은 곳은 0, 방문한 곳은 이전 visited에 +1을 해주며 진행해 나간다.

 

from collections import deque

N, M = map(int, input().split())
miro = []
for i in range(N):
    data = input()
    data1 = []
    for j in data:
        data1.append(int(j))
    miro.append(data1)

visited = [[0] * M for i in range(N)]
#print(visited)

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
queue = deque()


def bfs(a, b):
    queue.append([a, b])
    visited[a][b] = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 0 and miro[nx][ny] == 1:
                    queue.append([nx, ny])
                    visited[nx][ny] = visited[x][y] + 1


bfs(0, 0)
print(visited[N - 1][M - 1])