알고리즘

BFS (너비 우선 탐색)

그래프나 트리에서 시작 노드와 가까운 노드부터 단계적으로 탐색하는 방식. 큐(Queue)로 구현한다.

핵심 포인트

• 최단 거리(가중치 없는 그래프) 보장 — DFS 는 보장 안 함
• 큐에 넣을 때 방문 표시하는 것이 올바른 구현
• 레벨 단위 처리(BFS 트리의 깊이) 쉽게 구분 가능
• 대표 문제: 최단 경로, 이분 그래프 판별, 다중 시작점 BFS