탐색 알고리즘 (5): 너비 우선 탐색 (BFS: Breadth-First Search)

1. 너비 우선 탐색이란?

너비 우선 탐색(BFS, Breadth-First Search)은 그래프나 트리를 탐색하는 대표적인 방법 중 하나로, 시작 노드에서 가까운 노드를 먼저 탐색한 후, 점차 더 깊은 노드를 탐색하는 방식으로 동작한다.

BFS는 큐(Queue, 선입선출 구조)를 활용하며, 최단 경로 탐색, 네트워크 분석, 퍼즐 해결 등 다양한 분야에서 사용된다.

2. 너비 우선 탐색의 동작 원리

BFS는 다음과 같은 과정으로 수행된다:

1. 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 하나 꺼내고, 해당 노드와 연결된 모든 인접 노드를 확인한다.
3. 인접 노드 중 아직 방문하지 않은 노드를 큐에 삽입하고 방문 처리를 한다.
4. 큐가 빌 때까지 2번과 3번 과정을 반복한다.

2.1 너비 우선 탐색 과정 예제

다음과 같은 그래프에서 BFS를 수행한다고 가정하자:

    1
   / \
  2   3
 / \    
4   5

 

BFS 탐색 순서 (시작 노드: 1):

1 → 2 → 3 → 4 → 5

2.2 너비 우선 탐색 예제 코드 (Java)

import java.util.*;

public class BFS {
    // 너비 우선 탐색 메서드
    public static void breadthFirstSearch(Map<Integer, List<Integer>> graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에서 노드 추출
            System.out.print(node + " "); // 노드 출력

            for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor); // 방문하지 않은 노드를 큐에 삽입
                    visited.add(neighbor); // 방문 처리
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 생성
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4, 5));
        graph.put(3, Collections.emptyList());
        graph.put(4, Collections.emptyList());
        graph.put(5, Collections.emptyList());

        System.out.println("BFS 탐색 순서:");
        breadthFirstSearch(graph, 1);
    }
}

3. 너비 우선 탐색의 성능 분석

BFS의 성능은 그래프의 노드 수(V)와 간선 수(E)에 따라 결정된다.

3.1 시간 복잡도

• O(V + E): 모든 노드와 간선을 한 번씩 탐색하기 때문

3.2 공간 복잡도

• O(V): 큐와 방문 기록을 저장하는 데 사용되는 메모리

4. 너비 우선 탐색의 장점과 단점

4.1 장점

• 최단 경로 보장: 무가중치 그래프에서 출발 노드로부터 목표 노드까지의 최단 경로를 보장
• 구현이 간단하며 다양한 문제에 적용 가능
• 순환 구조에서 무한 루프에 빠지지 않도록 예방 가능

4.2 단점

• 메모리 사용량: 큐에 저장된 노드 수에 따라 메모리 사용량이 많아질 수 있음
• 가중치 그래프에는 적합하지 않음 (다익스트라 알고리즘 사용 필요)

5. 너비 우선 탐색의 활용 및 개선 방법

5.1 활용 사례

• 최단 경로 탐색: 지도에서 최단 거리 찾기 (GPS 경로 탐색)
• 네트워크 분석: 그래프의 연결 여부 확인
• 퍼즐 해결: 최소 이동 횟수를 찾는 문제 (예: 8-퍼즐, 미로 탐색)

5.2 개선 방법

• 양방향 BFS: 시작점과 목표 지점에서 동시에 탐색해 성능 향상
• 메모리 최적화: 방문 체크 배열을 활용해 메모리 사용량 줄이기

6. 너비 우선 탐색 vs 깊이 우선 탐색

특징BFSDFS

탐색 방식	너비 우선 (레벨 순서 탐색)	깊이 우선 (경로 끝까지 탐색)
구현 자료구조	큐 (FIFO)	스택 (LIFO) 또는 재귀 호출
시간 복잡도	O(V + E)	O(V + E)
공간 복잡도	O(V)	O(V)
최단 경로 보장	✅	❌
무한 루프 위험	방문 체크로 방지 가능	방문 체크 없으면 무한 탐색
활용 사례	최단 경로, 네트워크 분석	경로 찾기, 퍼즐 해결

7. 결론

너비 우선 탐색(BFS)은 그래프에서 최단 경로를 찾는 데 매우 유용한 알고리즘으로, 다양한 문제 해결에 널리 사용된다. 큐를 활용한 구현으로 간단하며, 탐색 순서를 보장하고 무가중치 그래프에서 최단 경로를 찾는 데 적합하다.

DFS와 비교했을 때 더 많은 메모리를 사용하지만, 목표 지점까지의 거리가 중요한 경우 BFS가 더 적합하다.