[Algorithm] BFS·DFS 보충 정리

BFS — 최단 경로

BFS는 최단 경로(최단 거리)를 구할 때 자주 쓴다. 단, 한계가 있다.

• 정점당 비용이 동일할 때만 최단 거리를 보장한다.
• 이 조건을 위배하면(간선마다 가중치가 다르면) BFS만으로는 최단 거리를 구할 수 없고, 별도로 그리디(예: 다익스트라)로 구현해야 한다.

동작 순서:

1. Queue에 출발점을 삽입한다.
2. 큐가 빌 때까지 반복한다.
   • 큐에서 맨 앞 원소를 꺼낸다.
   • 그 원소를 사용(처리)한다.
   • 자식(인접 정점)을 탐색해 큐에 넣는다.

한 점에서 같은 깊이(depth) 로 퍼져 나가며 찾는 방식이라, 퍼져 나가는 과정에서 자연스럽게 최단 거리를 찾는다.

변형 BFS

기본 BFS는 큐가 빌 때까지 무작정 돌지만, “어디까지 돌지”를 제어하는 변형도 알아두면 좋다. 한 번에 다 빼지 않고 특정 단계까지만 돌고 나머지는 나중에 처리하는 식으로 다룰 수 있다.

DFS

DFS는 최단 거리와는 전혀 다르다(최단성을 보장하지 않는다).

• 한 방향으로 끝까지 들어가다가 갈 곳이 없으면 되돌아와 다시 탐색한다.
• 보통 재귀로 계속 탐색한다.