백준 2178번 : 미로 탐색 in Python
위 문제는 좌상단에서 출발해 우하단까지 도착하는 미로의 최단거리를 구하는 문제로, 그래프 탐색 알고리즘 중 BFS를 이용해서 해결할 수 있다.
BFS는 너비 우선 탐색으로, 그래프의 한 점과 인접한 점들을 순차적으로 탐색한 후 탐색한 점들의 인접한 점들 중 탐색하지 않은 점들을 탐색해 나가면서 모든 점을 탐색하는 알고리즘이다. 이를 이용해서 그래프 내에서 어떤 한 점과 다른 한 점 간의 최단거리를 구할 수 있다.
그렇다면 어떻게 최단거리를 구할 수 있을까? 우선 BFS를 구현하기 이전에 이를 보조하는 queue와 미로와 같은 크기의 distance라는 행렬을 만든다. 그 다음에 BFS를 구현하는데, 우선 시작 위치를 queue에 넣고 미로 행렬의 시작 위치에 해당하는 값을 시작 위치를 방문했다는 의미로 -1로 바꾼다. 그리고 distance 행렬의 시작 위치에 해당하는 값을 1로 바꾼다.
그 다음에 queue의 길이가 0이 아닐 동안 계속 순회하는 while loop을 만들고 while loop 내부에서 queue의 원소(미로의 어떤 위치)를 후입선출 방식으로 하나 꺼낸다. 그리고 그 위치에 대해 위치와 상하좌우로 인접한 네 위치 중 미로의 인덱스 범위를 만족하면서 미로의 해당 위치에서의 값이 1인 위치를 queue에 추가한다. 그리고 맨 처음에 시작 위치에 했던 방식처럼 미로 행렬의 해당 위치에 해당하는 값을 -1로 바꾸고 distance 행렬의 해당 위치의 값을 기존의 위치에 해당하는 distance 행렬에서의 값에 1을 더한 값으로 바꾼다.
이러한 방식으로 계속 진행하면 언젠가 미로의 모든 지점을 방문하게 되고, distance 행렬의 각 원소에는 시작 위치로부터 해당 위치까지 도달 가능한 경우 해당 위치까지 가는 최단 거리가 있게 된다. 따라서 distance의 (N-1, M-1) 원소를 통해 미로의 좌상단에서 우하단까지 가는데 최단 거리를 알 수 있다.
BFS를 통해 최단거리를 구할 수 있다는 것의 증명은 엄밀히 하자면 생각보다 복잡하다. 직관적으로 얘기하면 BFS는 하나의 원소에서 출발해 그 원소와 인접한 원소들을 탐색하고, 그 다음에는 그 원소들과 인접한 원소들 중 탐색하지 않은 원소를 탐색해 나가는데, 이는 처음 원소로부터 최단거리가 1인 원소를 찾고, 그 다음에는 최단거리가 2인 원소를 찾아나가면서 이를 계속 반복하는 과정이라고 생각할 수 있다. 그러므로 이러한 과정을 목적지에 도달할 때까지 반복하면 목적지까지의 최단거리를 구할 수 있는 것이다.
이를 코드로 구현하면 다음과 같다.
# 동서남북을 나타내는 배열
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
N, M = map(int, input().split())
# 미로를 담기 위한 행렬
maze = []
for _ in range(N):
arr = []
s = input()
for c in s:
arr.append(int(c))
maze.append(arr)
# 최단거리를 담기 위한 행렬
distance = [[0]*M for _ in range(N)]
# BFS를 보조하는 queue
queue = []
def BFS(x, y):
maze[y][x] = -1
queue.append([x, y])
distance[y][x] = 1
while len(queue) > 0:
[i, j] = queue.pop(0)
for k in range(4):
next_i = i + dx[k]
next_j = j + dy[k]
# 인덱스의 범위를 주의해야 한다.
if 0<=next_i<M and 0<=next_j<N and maze[next_j][next_i] == 1:
maze[next_j][next_i] = -1
queue.append([next_i, next_j])
distance[next_j][next_i] = distance[j][i] + 1
BFS(0, 0)
print(distance[N-1][M-1])