[백준/2178] 미로 탐색 | BFS와 최단 경로
BFS와 최단 경로
BFS는 최단거리와 관련있다. 왤까?
BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다.
BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다.
bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다.
그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다.
이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다.
결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다.
흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;;
예시를 보자.
시작점 A에서 F까지의 최단경로를 알아본다고 했을 때 bfs를 진행하면서 F를 처음 방문하는 순간을 생각해보면
그 순간에 거리가 1인 node들은 이미 다 방문을 했고, 거리가 2인 node들을 방문하고 있을 것이다.
만약 A에서 F까지의 최단 거리가 1이라면 거리가 1인 node를 찾을 때 이미 F를 방문했을 것이다.
그런데! F를 처음 방문하는 순간에는 거리가 2인 node였고, A에서 F까지의 최단 거리는 2일 수밖에 없다는 것이다.
처음 방문한 순간이 최단거리니까!!
이때 시작점에서부터 F까지의 경로를 저장해놓으면 최단 경로를 구할 수 있다.
2178번 미로 탐색
문제 해설
이 문제에서는 (1,1)에서 (N,M)으로 이동할 때의 최단거리를 물어봤으니까 bfs 알고리즘과 구현을 활용하여 시작점에서부터 목적지까지의 최단 경로를 저장하면서 미로를 탐색하면 답을 구할 수 있다.
최종 코드
import sys
from collections import deque
input = sys.stdin.readline
d = [(0,1),(0,-1),(-1,0),(1,0)]
q = deque()
# 최단 경로 -> BFS
def bfs(x, y) :
q.append((x,y))
while q:
x, y = q.popleft()
for dx, dy in d :
nx, ny = x+dx, y+dy
if 0 <= nx < n and 0 <= ny < m:
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y]+1
q.append((nx, ny))
return graph[n-1][m-1]
# 초기 세팅
n,m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
print(bfs(0,0))알게된 점
이 알고리즘을 어떨 때 어떻게 왜 쓰는지 이해하는 게 중요한 것같다.
복잡한 구현이 나와도 원리를 알고 연습을 많이 하면 어떻게든 잘 녹여낼 수 있으니까..
이번 기회에 bfs가 왜 최단경로를 구하는 데에 쓰이는지 정확하게 이해를 했다.
dfs와 bfs 지식에 대한 정확도를 더 높여야겠다.