[백준] 2178 : 미로 탐색

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

2178번: 미로 탐색

---

코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
maze = [list(map(int, list(sys.stdin.readline().strip()))) for _ in range(N)]
row_rot = [-1, 0, 1, 0]
col_rot = [0, 1, 0, -1]

dq = deque([[0, 0]])
while dq:
    row_tmp, col_tmp = dq.popleft()
    for k in range(4):
        row_num = row_tmp + row_rot[k]
        col_num = col_tmp + col_rot[k]
        if 0 <= row_num < N and 0 <= col_num < M and maze[row_num][col_num] == 1:
            maze[row_num][col_num] = maze[row_tmp][col_tmp] + 1
            dq.append([row_num, col_num])
else:
    print(maze[N-1][M-1])

풀이

 위 문제와 같이 '최단 거리'를 찾아야 하는 문제는 BFS를 이용하면 된다.

 시작 위치에서 도착 위치로 이동할 수 있는 경우만 입력으로 주어지기 때문에 dq에 시작 위치 인덱스를 초기값으로 담아두고, 미로 크기만큼 전부 돌 필요없이 dq가 빈 리스트가 될 때까지만 돌면 된다. (즉, 인접 행렬 크기에 해당하는 N * M 만큼을 이중 for문을 통해 모두 돌 필요가 당연히 없음 !)

 변수 설명은 아래와 같다.

row_rot, col_rot는 미로의 특정 위치에서 상하좌우로 뻗어나가기 위한 회전 인덱스 번호이다.

row_tmp, col_tmp은 미로의 특정 위치에서 상하좌우로 뻗어나갔을 때의 인덱스 번호이다.

row_num, col_num은 미로의 특정 위치에서 상하좌우로 뻗어나갔을 때의 해당 위치에서의 최단 거리이다.

 dq 안의 값을 하나씩 뽑아내면서 상하좌우 방향에서 1) 해당 행 인덱스 번호가 범위 내에 있는지, 2) 해당 열 인덱스 번호가 범위 내에 있는지, 3) 해당 인덱스에서의 미로의 값이 1인지 검사하여 맞다면 최단 거리를 업데이트하고 dq에 해당 인덱스 번호를 추가한다. 그리고 dq의 값이 빈 리스트가 된다면 도착 위치에 도달했다는 의미이므로 도착 위치에서의 최단 거리를 출력한다.