왜 최단거리 문제에 BFS를 사용하는가?

BFS란 무엇인가?

간단하게 알아보면, Breathe First Search의 약자로 넓이 우선 탐색 알고리즘이다.

1. 시작 노드에서 인접한 노드를 대기 큐에 저장한다.

2. 대기 큐에서 노드를 하나 추출해 방문한다.

3. 추출한 노드와 인접한 노드를 대기 큐에 저장한다.

4. 그래프 전부를 탐색할 때까지 2, 3을 반복한다.

 

그렇다면 왜 최단거리 문제를 풀 때 BFS를 사용하는가?

해당 이유는 BFS가 탐색하는 규칙을 살펴보면 알 수 있다. BFS의 경우 넓이를 우선으로 탐색하기 때문에 시작 노드와 거리가 1인이 노드를 전부 탐색하고, 다음으로 거리가 2인 노드들... 탐색하는 노드가 시작 노드로부터의 거리가 점차 증가한다. 탐색 중 거리를 늘려간다면 최소 거리가 나오기 때문에 BFS를 사용한다.

 

참고

https://nulls.co.kr/graph/141

 

학습 24.01.18

느낀점 생각보다 단순한 이유였지만 알게 되어 기분이 좋았다.