C# - BFS (너비 우선 탐색) / DFS (깊이 우선 탐색)

자료구조는 크게 두 가지로 나뉜다.

 

• 선형 구조: 데이터가 일렬로 이어지는 구조. 예를 들어 배열, 리스트, 큐, 스택 등이 있다. 한 원소 다음에 또 다른 원소가 순차적으로 이어진다.
• 비선형 구조: 데이터가 계층적 혹은 망 형태로 이어진 구조. 트리(Tree), 그래프(Graph) 등이 대표적이다. 한 노드에서 여러 갈래로 뻗어 나가며, 선형 구조보다 더 복잡한 관계를 표현할 수 있다.

 

이번 글에서는 비선형 구조의 BFS, DFS에 대해 이야기해 볼 것이다.

 

---

BFS : Breadth First Search ( 너비 우선 탐색 )

BFS는 가까운 곳부터 차례대로 탐색하는 방법이다.

시작 노드에서 출발해 인접한 노드들을 먼저 탐색하고, 그 다음 단계로 더 멀리 있는 노드들을 탐색한다.

그렇기 때문에 최단 경로 탐색에 유리하지만 메모리를 많이 사용한다는 단점이 있다.

RTS 게임에서의 최단 경로 계산 같은 경우에 사용하기 좋다.

 

 

BFS의 진행 순서를 표현한 그림이다.

A → B → C → D → E → F → G

이런 식으로 가장 가까운 노드를 먼저 탐색한 뒤,

그 다음 그 노드들과 연결돼있는 노드들을 탐색하는 방식이다.

 

BFS는 큐(Queue)를 사용해 구현할 수 있다.

 

예시 코드

public void BFS(Node<T> start, Node<T> target)
{
    Queue<Node<T>> queue = new Queue<Node<T>>(); // 임시로 큐 생성
    List<Node<T>> visited = new List<Node<T>>(); // 방문 기록을 List로 관리

    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        Node<T> current = queue.Dequeue();

        if(visited.Contains(current))
        {
            continue;
        }

        Console.WriteLine($"지하철 역 방문: {current.Value}"); // 방문역 출력
        visited.Add(current); // 방문했다고 기록

        if (current.Equals(target))
        {
            Console.WriteLine($"목표 역 {target.Value} 발견!");
            return;
        }

        foreach (var neighbor in current.Neighbors)
        {
            if(visited.Contains(neighbor) == false) // 이미 방문한 노드는 방문 예정 큐에 넣지 않음
            {
                queue.Enqueue(neighbo);
            }
        }

    }
    Console.WriteLine("경로 탐색 실패");
}

 

 

 

---

DFS : Depth First Search ( 깊이 우선 탐색 )

DFS는 이름 그대로 깊게 타고드는 탐색 방법이다.

시작 노드에서 출발해 한 갈래를 끝까지 탐색하며, 더 이상 진행할 수 없을 때 이전 분기점으로 돌아가 다른 갈래를 탐색한다.

모든 경로를 끝까지 확인해야 하는 경우에 적합하며 메모리 사용량이 BFS 보다 적다.

하지만 최단 경로를 보장하지 못한다고 한다.

 

 

 

DFS의 진행 순서를 표현한 그림이다.
A → B → D → E → C → F → G
이런 식으로 한 쪽 라인을 전부 탐색하고, 이전 분기 노드를 다시 끝까지 탐색하고를 반복하는 방식이다.

그런데 여기서...

이 두 진행 순서를 봤을때 D처럼 좌측 끝에 탐색 목표가 있는 경우, 탐색 속도가 더 빠를 수도 있는 거 아닌가?

라는 의문이 들었다.

A B D vs A B C D 인데 메모리를 더 많이 쓴다?
당연히 A B D 가 빠를 것이다.
하지만 비선형 자료 구조는 노드의 연결이 꼭 하나만 있다는 법이 없다.
즉 A B D 로 D로의 경로를 찾았으나, 다시 뒤에서 검색해보니 A에서 D로 바로 접근할 수 있는 최단 경로가 따로 있을 수 있다.

즉 전체를 순회하기 전에는 DFS로 구한 경로가 최단 경로 라는 보장을 받지 못하기 때문에, 결국 최단 경로를 알기 위해서는 전부 순회해야만 하는 것이나 다름 없기 때문에 최단경로 검색에 BFS가 더 적합하다는 이야기다.


DFS는 스택(Stack)이나 재귀함수를 이용해 구현할 수 있다.

 

 

예시 코드

public void DFS(Node<T> start, Node<T> target)
{
    Stack<Node<T>> stack = new Stack<Node<T>>(); // 임시로 큐 생성
    List<Node<T>> visited = new List<Node<T>>(); // 방문 기록을 List로 관리

    stack.Push(start);
    while (stack.Count > 0)
    {
        Node<T> current = stack.Pop();

        if(visited.Contains(current))
        {
            continue;
        }

        Console.WriteLine($"지하철 역 방문: {current.Value}"); // 방문역 출력
        visited.Add(current); // 방문했다고 기록

        if (current.Equals(target))
        {
            Console.WriteLine($"목표 역 {target.Value} 발견!");
            return;
        }

        foreach (var neighbor in current.Neighbors)
        {
            if(visited.Contains(neighbor) == false) // 이미 방문한 노드는 방문 예정 큐에 넣지 않음
            {
                stack.Push(neighbor);
            }
        }

    }
    Console.WriteLine("경로 탐색 실패");
}

 

 

 

재귀 함수를 이용해서 이렇게 구성해 볼 수도 있다.

 

public void DFS(Node<T> current, Node<T> target, HashSet<Node<T>> visited)
{
    if (current == null) return;

    // 이미 방문했다면 중복 방지
    if (visited.Contains(current)) return;

    // 현재 노드 방문
    Console.WriteLine($"지하철 역 방문: {current.Value}");
    visited.Add(current);

    // 목표 노드 도착 확인
    if (current.Equals(target))
    {
        Console.WriteLine($"목표 역 {target.Value} 발견!");
        return;
    }

    // 이웃 노드 재귀 호출
    foreach (var neighbor in current.Neighbors)
    {
        DFS(neighbor.To, target, visited);
    }
}

 

---

 

정리

	BFS	DFS
구현 방식	큐	스택 / 재귀
탐색 순서	가까운 노드부터	하나의 줄기 끝까지 간 다음 순회
장점	최단 경로 보장	메모리 적게 사용
단점	메모리 사용량 많	최단 경로 보장 X
게임 활용	최단 경로 탐색, 길 찾기	던전 탐험, 숨겨진 아이템 찾기

 

 

 

BFS와 DFS의 차이

• BFS는 큐를 사용해 가까운 노드부터 탐색, 최단 경로 보장.
• DFS는 스택/재귀를 사용해 깊이 들어감, 최단 경로 보장 불가.
• 보장 불가라는 말은, 운 좋게 짧은 경로를 먼저 찾을 수도 있지만(이 자체만으로도 보장성이 아님), 그것을 최단 경로라 보장하지는 못하기 때문에 최단 경로 탐색이라고는 할 수 없다.

 

BFS, DFS 사용처

• BFS: 최단 거리 필요, 길찾기, 네트워크 최단 전송 경로.
• DFS: 모든 경로 탐색, 미로/던전 탐험, 조합/백트래킹 문제.

 

시간복잡도와 공간복잡도

• 그래프의 정점 개수 V, 간선 개수 E라 할 때,
  • BFS: O(V+E)
  • DFS: O(V+E)
• 시간복잡도는 동일하지만, BFS는 큐에 많은 노드를 보관해야 하므로 공간복잡도가 커질 수 있다.