2178번 - 미로 탐색(Python)

 

풀이

bfs를 이용해 이동 거리를 계산한다.

dp의 초기값을 모두 -1로 설정하고, 이를 통해 방문 여부를 확인한다.

 

다음 좌표가 이동 가능하고, dp값이 -1이라면 방문한 적이 없다는 뜻이므로 현재 좌표의 dp값인 dp[y][x] 값에서 1을 더해 저장한다.

dp값이 -1이 아니라면 이미 방문한 적이 있다는 뜻이므로 넘어간다.(bfs에서는 먼저 방문한 경로가 최단 경로)

코드

from collections import deque


N, M = map(int, input().split())
maze = [input() for _ in range(N)]
dp = [[-1 for _ in range(M)] for _ in range(N)]
dp[0][0] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque([[0, 0]])

while queue:
    node = queue.popleft()
    y, x = node[0], node[1]

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < N and 0 <= nx < M and maze[ny][nx] == "1" and dp[ny][nx] == -1:
            dp[ny][nx] = dp[y][x] + 1
            queue.append([ny, nx])

print(dp[N-1][M-1])