너비 우선 탐색 (BFS)의 개념 및 구현

너비 우선 탐색(BFS, Breadth-First Search)은 그래프 탐색 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 탐색해 나가는 방식입니다. 이번 포스팅에서는 BFS의 개념, 동작 원리, 장단점, 그리고 C# 구현 예제를 통해 BFS를 깊이 있게 알아보겠습니다.

---

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

BFS는 그래프나 트리 구조에서 데이터를 탐색하거나 검색할 때 사용되는 알고리즘으로, 계층적으로 탐색하는 것이 특징입니다. 특정 노드에서 시작하여 같은 계층의 노드(인접 노드)를 모두 방문한 후, 다음 계층으로 이동합니다.

---

1.1. BFS의 동작 원리

1. 시작 노드를 방문하고, 이를 큐(Queue)에 삽입합니다.
2. 큐에서 노드를 하나씩 꺼내 해당 노드와 연결된 모든 인접 노드를 큐에 삽입합니다.
3. 이미 방문한 노드는 다시 방문하지 않습니다.
4. 큐가 빌 때까지 위 과정을 반복합니다.

---

1.2. BFS 탐색 방식

BFS는 선입선출(FIFO) 방식의 큐를 활용하여 탐색을 진행합니다. 탐색 순서는 계층별로 진행되므로, 먼저 방문한 노드의 인접 노드가 우선적으로 탐색됩니다.

---

2. BFS의 장단점

2.1. 장점

• 최단 경로 보장: 가중치가 없는 그래프에서 BFS는 시작 노드에서 특정 노드까지의 최단 경로를 항상 보장합니다.
• 모든 경로 탐색 가능: 특정 조건을 만족하는 경로를 찾을 때 유용합니다.

2.2. 단점

• 메모리 사용량: 큐를 사용하므로 탐색 중 많은 노드를 저장해야 하며, 깊이가 깊거나 노드가 많은 그래프에서는 메모리 사용량이 커질 수 있습니다.
• 가중치 처리 불가능: BFS는 가중치를 고려하지 않으므로, 가중치가 있는 그래프에서는 다익스트라 알고리즘이 더 적합합니다.

---

3. BFS의 구현 (C# 예제)

BFS를 구현하기 위해 그래프를 인접 리스트(Adjacency List)로 표현합니다.

3.1. 그래프 표현

using System;
using System.Collections.Generic;

public class Graph
{
    private Dictionary<int, List<int>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<int, List<int>>();
    }

    public void AddEdge(int start, int end)
    {
        if (!adjacencyList.ContainsKey(start))
        {
            adjacencyList[start] = new List<int>();
        }
        adjacencyList[start].Add(end);

        if (!adjacencyList.ContainsKey(end))
        {
            adjacencyList[end] = new List<int>();
        }
        adjacencyList[end].Add(start); // 무방향 그래프
    }

    public Dictionary<int, List<int>> GetGraph()
    {
        return adjacencyList;
    }
}

 

---

3.2. BFS 구현

public class BreadthFirstSearch
{
    public void BFS(int startNode, Dictionary<int, List<int>> graph)
    {
        var visited = new HashSet<int>(); // 방문 기록
        var queue = new Queue<int>();    // 탐색을 위한 큐

        // 시작 노드를 큐에 삽입하고 방문 처리
        queue.Enqueue(startNode);
        visited.Add(startNode);

        while (queue.Count > 0)
        {
            // 큐에서 노드를 꺼내 출력
            int currentNode = queue.Dequeue();
            Console.WriteLine(currentNode);

            // 인접 노드 탐색
            foreach (var neighbor in graph[currentNode])
            {
                if (!visited.Contains(neighbor))
                {
                    queue.Enqueue(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }
}

 

---

3.3. 실행 예시

public class Program
{
    public static void Main()
    {
        // 그래프 생성
        var graph = new Graph();
        graph.AddEdge(1, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(2, 5);
        graph.AddEdge(3, 6);
        graph.AddEdge(3, 7);

        // BFS 실행
        Console.WriteLine("BFS 탐색 순서:");
        var bfs = new BreadthFirstSearch();
        bfs.BFS(1, graph.GetGraph());
    }
}

 

---

3.4. 실행 결과

위 코드를 실행하면 아래와 같은 탐색 순서를 출력합니다:

BFS 탐색 순서:
1
2
3
4
5
6
7

 

---

4. BFS의 응용 분야

1. 최단 경로 탐색
   가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 찾는 데 사용됩니다.
   • 예: 미로 문제, 지하철 노선 최단 거리 탐색
2. 네트워크 연결 상태 확인
   네트워크 내의 모든 노드가 연결되어 있는지 확인하는 데 유용합니다.
3. 레벨 탐색
   트리 또는 그래프에서 특정 깊이에 있는 모든 노드를 탐색할 때 활용됩니다.
4. Web 크롤링
   웹 페이지의 링크를 따라 사이트를 탐색하는 크롤러에 사용됩니다.

---

5. BFS와 DFS 비교

특성	BFS	DFS
탐색 순서	계층적으로 탐색	깊이 우선 탐색
메모리 사용량	큐로 인해 메모리 사용량이 많을 수 있음	재귀 호출로 인해 스택을 사용
특징	최단 경로 보장	특정 경로 또는 모든 경로 탐색
사용 사례	최단 경로, 계층 탐색	백트래킹, 경로 탐색

---

BFS는 그래프 탐색의 기본적인 알고리즘으로, 특정 문제에서 최단 경로를 보장하기 때문에 매우 유용합니다. 그러나 메모리 사용량이 많아질 수 있으므로, 그래프의 크기와 문제의 특성을 고려해 사용해야 합니다. BFS의 동작 원리와 구현을 이해하면 다양한 탐색 문제를 해결할 수 있는 강력한 도구를 갖게 될 것입니다.