미로 N * M
현재 위치 1,1
출구 N, M
1칸씩 이동
괴물 있으면 0 없으면 1
따라서 시작칸과 마지막칸은 항상 1
이때 탈출하기 위해 움직여야하는 최소 칸의 개수?
미로의 개념을 상기해보면, 결국 내가 있는 위치에서 주변을 보고 그 방향을 정해야한다.
즉, 나와 가까운 위치부터 탐색을 해야한다는 걸 의미하고 따라서 BFS를 쓰는게 맞다.
주변을 보고 1이면 이동, 0이거나 막혀있으면 다른 방향 탐색을 반복.
최소 이동 거리 개념은 사실 이전에 방문했던 곳을 다시 방문하면 안된다는 이야기와 같다.
따라서 재방문은 없이 바로 출구까지 갈수 있도록 해야한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from collections import deque
# 미로 크기
n, m = map(int, input().split())
# 2차원 미로 그래프
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 상, 하, 좌, 우 이동 시 x,y 변화량
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]
# 0이면 무시
if graph[nx][ny] == 0:
continue
# 그래프 벗어나면 무시
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
# 1이면 이동하고 최단 거리 카운트
# 최단 거리에 해당하는 노드에 카운트를 +1씩해서 표시
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))
최단 거리를 따라 이동하면서, 최단거리에 속하는 노드에 들릴때 카운트를 +1씩하는 방식을 기억해둘 필요가 있다.
유사한 방식의 최단거리 문제는 이렇게 풀면 목적지의 값을 출력함으로써 바로 해결가능하기 때문이다.