너비 우선 탐색(BFS)이란?

너비 우선 탐색은 그래프 또는 트리를 탐색할 때, 한 노드에서 시작하여 레벨별로 인접한 노드를 먼저 탐색하는 알고리즘입니다.

• 큐(Queue): BFS는 큐를 사용하여 방문할 노드들을 관리합니다.

• 레벨별 탐색: BFS는 각 노드의 레벨별로 인접한 노드를 탐색합니다.

• 최단 경로: BFS는 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 자주 사용됩니다.

• 시간 복잡도: (O(|V| + |E|)), 여기서 (|V|)는 정점의 수, (|E|)는 간선의 수입니다.

1. 노드 선택: 탐색을 시작할 노드를 선택합니다.

2. 방문 및 탐색: 선택한 노드를 방문하고, 인접한 노드를 큐에 추가합니다.

3. 레벨별 탐색: 큐에서 노드를 꺼내 방문하고, 그 인접 노드들을 큐에 추가합니다.

4. 탐색 완료: 큐가 비어있을 때 탐색을 종료합니다.

• 너비 우선: 각 레벨의 노드를 탐색한 후 다음 레벨의 노드로 넘어갑니다.

• 단층 탐색(Layered Search): 노드를 레벨별로 탐색하여 레벨이 동일한 노드들을 먼저 방문합니다.

• 최단 경로 탐색: BFS는 무방향 그래프에서 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 효과적입니다.

• 탐색 순서: 노드의 탐색 순서는 큐의 구현 방식과 시작 노드에 따라 달라집니다.

• 장점: 최단 경로를 찾는데 효과적이고, 모든 레벨의 노드를 방문합니다. 너비 우선 탐색은 순환 경로가 있는 그래프에서도 잘 작동합니다.

• 단점: BFS는 DFS에 비해 메모리 사용량이 많을 수 있습니다. 모든 인접 노드를 저장해야 하기 때문에 큰 그래프에서는 메모리 부담이 클 수 있습니다.