BFS()는 공짜로 최단 경로를 보장하지 않는다(Feat. Predecessor)

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

[그래프] 26. 최단 경로용 BFS

아래와 같은 빈 큐와 그래프가 있다고 가정하자.

여기에 BFS 알고리즘을 사용할 것이다.

각 Node 의 predecessor 는 보기 편하게 표로 나타내겠다.

 

먼저 시작점 Node를 방문했다고 표시한다.

시작점은 아무데서도 오지 않았다. 그러니 이전 Node가 없는 것이다.

predecessor 는 없다고 표시한다.

시작점 Node A 를 큐에 넣는다.

 

큐에서 가장 앞에 있는 Node를 꺼낸다.

A 가 나온다. A 와 인접한 Node 들을 하나씩 본다.

 

Node B 는 아직 방문하지 않은 Node 이다.

B 를 방문했다고 표시한다.

B 는 A 를 통해서 방문했기 때문에 predecessor 를 A 라고 한다.

B 를 큐에 넣어준다.

 

다음은 A 에 인접한 다른 Node C 를 본다.

C 도 아직 방문하지 않은 Node 이다.

C 를 방문했다고 표시한다.

C 는 A 를 통해서 방문했기 때문에 predecessor 를 A 라고 한다.

C 를 큐에 넣어준다.

 

이제 큐에 들어있는 가장 앞 Node 를 꺼낸다.

B 가 나온다.

B 에 인접한 Node 들을 본다.

 

A 는 이미 방문한 Node 이기 때문에 건너 뛴다.

 

Node D 는 아직 방문하지 않은 Node 이다.

방문했다고 표시한다.

D 는 B를 통해서 방문했기 때문에 predecessor 에 B 를 넣는다.

D 를 큐에 넣는다.

 

큐에 들어있는 가장 앞 Node 를 꺼낸다.

C 가 나온다.

C 에 인접한 Node 들은 본다.

 

A 는 이미 방문한 Node 이다. 건너 뛴다.

 

E 는 아직 방문하지 않은 Node 이다.

방문했다고 표시를 한다.

E 는 C 를 통해 방문했기 때문에 predecessor 에 C 를 넣는다.

E 를 큐에 넣는다.

 

F 도 아직 방문하지 않은 Node 이다.

방문했다고 표시하자.

F 는 C 를 통해 방문했기 때문에 predecessor 에 C 를 넣는다.

F 를 큐에 넣는다.

 

큐에 들어있는 가장 앞 Node 를 꺼낸다.

나머지는 전부 인접한 Node 를 방문한 기록이 있어서 전부 아무 처리도 안한다.

 

이렇게 큐 안에 모든 Node 들이 없어져서 BFS 가 끝난다.

 

이제 가져온 정보로 시작점 A 에서 F 까지의 최단 경로를 알아보자.

 

그러면 목표 지점인 F 에서 시작한다.

F 의 predecessor 는 C 이다.

C 의 predecessor 는 A 이다.

A 는 predecessor 가 없다.

 

이 순서를 뒤집어 본다.

그럼 A - C - F 가 된다.

바로 이게 A 에서 F 까지 최단 경로이다.

 

마찬가지로 A 에서 D 까지 최단 경로를 구하고 싶다고 하자.

그러면 목표 지점인 D 에서 시작한다.

D 의 predecessor 는 B 이다.

B 의 predecessor 는 A 이다.

A 의 predecessor 는 없다.

 

이 순서를 뒤집어 본다.

그럼 A - B - D 가 된다.

바로 이게 A 에서 D 까지 최단 경로이다.

 

정리해 보면 BFS를 하면서 각 Node 가 어디서 왔는지, predecessor 를 저장했다.

이 predecessor 를 구하면 시작점에서 원하는 Node 까지의 경로를 구할 수 있고, 이 경로가 바로 최단 경로이다.

 

이렇게 도착점부터 시작점까지 거꾸로 찾아가는 걸 Backtracking 이라고 한다.