BFS(너비 우선 탐색, Breadth-First Search) 알고리즘
BFS는 그래프 또는 트리에서 너비 우선으로 노드를 탐색하는 알고리즘입니다. BFS는 시작 노드에서 출발하여, 그 노드와 연결된 노드들을 먼저 모두 탐색하고, 그 후에 각 노드에서 연결된 노드를 차례대로 탐색합니다. 이 과정은 큐(Queue) 자료구조를 이용하여 구현합니다.
BFS의 주요 특징은 가까운 노드부터 차례대로 탐색하므로, 목표 노드까지의 최단 경로를 찾는 데 유용합니다.
BFS 동작 방식:
1. 시작 노드를 큐에 넣습니다.
2. 큐에서 노드를 하나 꺼내고, 그 노드를 방문합니다.
3. 그 노드에 연결된 인접 노드들을 큐에 넣습니다.
4. 큐가 비어 있을 때까지 2번과 3번을 반복합니다.
5. 모든 노드를 방문할 때까지 탐색을 계속합니다.
BFS의 특징:
- 시간 복잡도: 그래프의 모든 노드와 간선을 한 번씩 처리하므로 O(V + E)입니다. (V: 노드의 수, E: 간선의 수)
- 공간 복잡도: 큐에 최대한 많은 노드가 들어갈 수 있으므로 O(V)만큼의 공간이 필요합니다.
BFS는 특히 최단 경로 문제, 최단 거리 계산, 레벨별 탐색 등에 유용하게 사용됩니다.
BFS 구현 (자바)
자바에서 BFS를 구현하려면 큐를 사용해야 합니다. 자바의 `Queue` 인터페이스를 구현한 LinkedList를 사용할 수 있습니다.
1. 그래프 표현
그래프는 인접 리스트 방식으로 표현합니다.
import java.util.*;
public class BFSExample {
private static Map<Integer, List<Integer>> graph = new HashMap<>();
// 그래프에 간선 추가
public static void addEdge(int v, int w) {
graph.putIfAbsent(v, new ArrayList<>());
graph.get(v).add(w);
}
// BFS - 너비 우선 탐색
public static void bfs(int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
// 시작 노드를 큐에 넣고 방문 표시
visited.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " "); // 현재 노드 출력
// 현재 노드와 연결된 모든 인접 노드를 큐에 추가
for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
public static void main(String[] args) {
// 간선 추가 (그래프 생성)
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(3, 6);
System.out.println("BFS 탐색 결과:");
bfs(1); // 시작 노드 1에서 BFS 탐색
}
}
설명:
1. addEdge: 그래프에 간선을 추가하는 메서드입니다. `v`와 `w`를 연결하는 간선이 추가됩니다.
2. bfs: BFS 알고리즘을 구현한 메서드입니다. 큐를 사용하여 너비 우선으로 그래프를 탐색합니다.
- 큐에 시작 노드를 넣고, 큐가 비어 있을 때까지 노드를 하나씩 꺼내면서 방문합니다.
- 방문한 노드의 인접 노드가 아직 방문되지 않았다면 큐에 넣습니다.
3. main: 그래프를 생성하고 BFS 탐색을 시작합니다.
출력 예시:
BFS 탐색 결과:
1 2 3 4 5 6
BFS의 특징:
- BFS는 각 레벨별로 노드를 탐색하기 때문에 트리나 그래프에서 최단 경로를 찾는 데 유용합니다.
- BFS는 큐(Queue)를 사용하여 선입선출(FIFO) 방식으로 노드를 탐색하므로, 가까운 노드를 먼저 방문합니다.
BFS가 유용한 문제 예시:
- 최단 경로 문제: BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용될 수 있습니다.
- 연결 요소 탐색: 그래프가 연결된 여러 부분 그래프를 가지고 있을 때, BFS를 사용하여 각 부분을 탐색할 수 있습니다.
- 레벨별 탐색: 각 노드를 레벨에 따라 탐색할 수 있으므로, 레벨 차이를 고려한 문제에 적합합니다.
요약:
- BFS는 너비 우선으로 노드를 탐색하며, 큐를 사용하여 구현합니다.
- 그래프에서 최단 경로를 찾을 때 주로 사용되며, 모든 노드를 한 번씩 방문하고 각 레벨을 차례대로 탐색합니다.