BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색) in C#

그래프 탐색 알고리즘인 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 다양한 문제 해결에 활용됩니다. 이번 글에서는 C#으로 구현한 BFS와 DFS 예제 코드와 함께 탐색 과정 테이블을 포함하여 설명하겠습니다.

그래프 구조

탐색을 수행할 그래프는 아래와 같은 구조를 가지고 있습니다.

그래프의 인접 리스트 표현

노드	인접 노드
1	2, 3, 4
2	5, 6
3	7
4	없음
5	없음
6	없음
7	없음

BFS (너비 우선 탐색)

BFS는 가까운 노드부터 차례대로 방문하는 탐색 방법으로, **큐(Queue, FIFO)**를 활용하여 구현됩니다.

1. BFS 알고리즘 동작 방식

탐색 시작 노드를 큐에 삽입하고 방문 처리
큐에서 노드를 꺼낸 후, 해당 노드의 인접 노드를 큐에 삽입
큐가 빌 때까지 위 과정을 반복

2. BFS 예제 코드 (C#)

using System;
using System.Collections.Generic;

class Program
{
    static void BFS(Dictionary<int, List<int>> graph, int start)
    {
        HashSet<int> visited = new HashSet<int>();
        Queue<int> queue = new Queue<int>();

        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            Console.Write(node + " ");

            foreach (int neighbor in graph[node])
            {
                if (!visited.Contains(neighbor))
                {
                    queue.Enqueue(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }

    static void Main()
    {
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>()
        {
            {1, new List<int>{2, 3, 4}},
            {2, new List<int>{5, 6}},
            {3, new List<int>{7}},
            {4, new List<int>()},
            {5, new List<int>()},
            {6, new List<int>()},
            {7, new List<int>()}
        };

        Console.WriteLine("BFS 탐색 결과:");
        BFS(graph, 1);
    }
}

3. BFS 탐색 과정 (큐 활용)

단계	큐(Queue) 상태	방문한 노드
초기	[1]	-
1	[2, 3, 4]	1
2	[3, 4, 5, 6]	1, 2
3	[4, 5, 6, 7]	1, 2, 3
4	[5, 6, 7]	1, 2, 3, 4
5	[6, 7]	1, 2, 3, 4, 5
6	[7]	1, 2, 3, 4, 5, 6
7	[]	1, 2, 3, 4, 5, 6, 7

DFS (깊이 우선 탐색)

DFS는 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방식으로, 스택(Stack, LIFO) 또는 재귀 함수를 활용하여 구현됩니다.

1. DFS 알고리즘 동작 방식

탐색 시작 노드를 방문하고 출력
방문한 노드의 인접 노드를 순차적으로 방문
더 이상 방문할 노드가 없으면 이전 노드로 돌아가 다른 경로 탐색

2. DFS 예제 코드 (C#)

using System;
using System.Collections.Generic;

class Program
{
    static void DFS(Dictionary<int, List<int>> graph, int node, HashSet<int> visited)
    {
        if (!visited.Contains(node))
        {
            Console.Write(node + " ");
            visited.Add(node);

            foreach (int neighbor in graph[node])
            {
                DFS(graph, neighbor, visited);
            }
        }
    }

    static void Main()
    {
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>()
        {
            {1, new List<int>{2, 3, 4}},
            {2, new List<int>{5, 6}},
            {3, new List<int>{7}},
            {4, new List<int>()},
            {5, new List<int>()},
            {6, new List<int>()},
            {7, new List<int>()}
        };

        Console.WriteLine("DFS 탐색 결과:");
        DFS(graph, 1, new HashSet<int>());
    }
}

3. DFS 탐색 과정 (재귀 활용)

단계	현재 방문한 노드	스택(Stack) 상태	방문한 노드
초기	1	[1]	-
1	1 → 2	[1, 2]	1
2	2 → 5	[1, 2, 5]	1, 2
3	5 (백트래킹)	[1, 2]	1, 2, 5
4	2 → 6	[1, 2, 6]	1, 2, 5
5	6 (백트래킹)	[1, 2]	1, 2, 5, 6
6	2 (백트래킹)	[1]	1, 2, 5, 6
7	1 → 3	[1, 3]	1, 2, 5, 6
8	3 → 7	[1, 3, 7]	1, 2, 5, 6, 3
9	7 (백트래킹)	[1, 3]	1, 2, 5, 6, 3, 7
10	3 (백트래킹)	[1]	1, 2, 5, 6, 3, 7
11	1 → 4	[1, 4]	1, 2, 5, 6, 3, 7
12	4 (백트래킹)	[1]	1, 2, 5, 6, 3, 7, 4
13	탐색 종료	[]	1, 2, 5, 6, 3, 7, 4

BFS vs DFS 비교

비교 항목	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 방식	가까운 노드부터 탐색	한 경로를 끝까지 탐색
자료구조	큐 (Queue)	스택(Stack) / 재귀(Recursion)
사용 목적	최단 거리 탐색 (가중치 없는 그래프)	백트래킹, 경로 탐색
메모리 사용량	많은 노드를 저장해야 하므로 높을 수 있음	스택 깊이에 따라 다름
실제 활용 예시	네트워크 라우팅, SNS 친구 추천	미로 찾기, 퍼즐 해결
시간 복잡도	O(V + E)	O(V + E)

활용 예제

BFS 활용 예시
- 최단 거리 탐색 (길찾기, 네트워크 라우팅)
- SNS 친구 추천 알고리즘
- AI 게임 탐색 (체스, 바둑 등)
DFS 활용 예시
- 백트래킹 (퍼즐, 미로 찾기, 게임)
- 웹 크롤링 (링크를 깊이 따라가는 방식)
- 그래프의 연결 요소 찾기

면접 예상 질문

Q1: DFS와 BFS의 차이점을 설명하세요.
A1: BFS는 가까운 노드부터 탐색하는 방식이고, DFS는 한 경로를 끝까지 탐색한 후 백트래킹하는 방식입니다. BFS는 큐를 사용하고, DFS는 스택이나 재귀를 사용합니다.

Q2: BFS와 DFS의 시간 복잡도는 어떻게 되나요?
A2: 둘 다 O(V + E)의 시간 복잡도를 가집니다. V는 노드 수, E는 간선 수입니다.

Q3: DFS의 반복문 구현이 가능한가요?
A3: 네, DFS는 스택을 이용하여 반복문으로도 구현할 수 있습니다.

Q4: BFS는 어떤 상황에서 유리한가요?
A4: 최단 경로를 찾는 문제에서 유리합니다. 예를 들어, 미로 찾기나 최단 거리 탐색 문제에서 효과적입니다.

Q5: DFS를 사용할 때 주의해야 할 점은?
A5: 재귀를 사용할 경우 스택 오버플로우가 발생할 수 있으므로 깊이가 깊은 그래프에서는 반복문 기반의 DFS를 고려해야 합니다.

Q6: BFS와 DFS 중 어떤 것을 선택해야 하나요?
A6: 최단 경로를 찾을 때는 BFS가 적합하며, 백트래킹이 필요한 경우 DFS를 사용합니다.

Q7: DFS의 단점은 무엇인가요?
A7: 깊은 탐색 시 스택 오버플로우가 발생할 수 있으며, 최단 경로 탐색에는 적합하지 않습니다.

Q8: BFS를 사용할 때 주의할 점은?
A8: 큐에 많은 노드를 저장해야 하므로 메모리 사용량이 증가할 수 있습니다.

BFS와 DFS는 다양한 문제 해결에 활용할 수 있는 중요한 알고리즘입니다. 탐색 목적에 맞는 알고리즘을 선택하여 효율적인 문제 해결을 해보세요! 🚀

Trend Info 2x