[백준/python] 2178 미로 탐색

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번 미로 탐색

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))