왜 그러한가?

어느날 코딩테스트 문제를 풀던 도중 BFS를 활용하는 문제가 있었다. BFS와 DFS의 사용이 익숙치않아 몇시간 가량 코드를 짜봤지만 정답이 나오지 않아 결국 해답을 볼 수 밖에 없었는데 해답을 보던 도중 이해할 수 없는 부분이 있었다.
while(!q.empty()) 문을 돌리던 도중 원하던 위치에 도달하자 break문으로 탈출해버린 것이다. 방금 도달한 그 방법이 최단거리를 보장하는 방법이라는 확신이 있었을까? 어째서 탈출했고 어째서 정답이었을까? 궁금하여 검색해보자 BFS를 이용하여 도달한 노드는 무조건 최단거리라는 사실을 알게되었다.
그 이유는 BFS의 매커니즘에 있었다. BFS는 기본적으로 시작점에 인접한 노드를 모두 방문한다. 그 다음 방문했던 노드들의 인접 노드를 모두 방문한다. 알기 쉽게 설명하자면 거리(깊이)가 1인 노드를 모두 방문한 뒤 2인 노드를 방문하기 시작하여 모두 방문한 뒤에야 3인 노드를 방문하는 것이다. 깊이 순으로 방문하기 때문에 BFS 루프를 가동하던 중 원하던 도착점에 도달하면 그 때가 최단거리임이 보장되는 것이다.
BFS와 DFS를 사용하는 문제가 매우 많고 앞으로도 많을 것인데 이러한 알고리즘의 특징을 잘 숙지해두는 것이 분명 중요할 것 같다.