[백준/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 지식에 대한 정확도를 더 높여야겠다.