깊이 우선 탐색 (DFS)의 개념 및 구현

깊이 우선 탐색(DFS, Depth-First Search)은 그래프 탐색 알고리즘 중 하나로, 가능한 한 깊이까지 탐색한 후, 더 이상 탐색할 수 없을 때 이전 단계로 돌아가는 방식으로 동작합니다. 이번 포스팅에서는 DFS의 개념, 동작 원리, 장단점, 그리고 C#을 활용한 구현 방법에 대해 알아보겠습니다.

---

1. 깊이 우선 탐색(DFS)이란?

DFS는 트리(Tree)와 그래프(Graph)와 같은 데이터 구조에서 데이터를 탐색하거나 검색하는 데 사용되는 알고리즘입니다. 이 알고리즘은 시작 노드에서 출발하여 가능한 한 깊이 있는 노드까지 탐색한 후, 다시 되돌아가 다른 경로를 탐색합니다.

---

1.1. DFS의 동작 원리

1. 시작 노드를 방문하고, 이를 방문했다고 표시합니다.
2. 방문한 노드와 연결된 첫 번째 자식 노드로 이동합니다.
3. 자식 노드를 방문한 후, 해당 노드의 다른 자식 노드를 탐색합니다.
4. 더 이상 탐색할 자식 노드가 없다면 직전 노드(부모 노드)로 되돌아갑니다.
5. 위 과정을 모든 노드를 탐색할 때까지 반복합니다.

---

1.2. DFS 탐색 방식

DFS는 두 가지 방식으로 구현할 수 있습니다:

• 재귀(Recursion): 함수 호출을 사용하여 깊이를 탐색
• 스택(Stack): 스택 자료구조를 사용하여 탐색

---

2. DFS의 장단점

2.1. 장점

• 공간 효율성: DFS는 경로를 추적하기 위해 상대적으로 적은 메모리를 사용합니다(재귀 호출 스택 또는 명시적 스택만 사용).
• 단순 구현: 재귀를 이용하면 구현이 간단합니다.
• 경로 탐색에 적합: 특정 경로를 찾거나 모든 경로를 탐색하는 문제에서 유리합니다.

2.2. 단점

• 무한 루프 가능성: 그래프가 순환을 포함하면 방문 여부를 체크하지 않을 경우 무한 루프에 빠질 수 있습니다.
• 최단 경로 보장 안됨: DFS는 깊이 우선으로 탐색하기 때문에 최단 경로를 찾는 문제에서는 적합하지 않습니다.

---

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

DFS를 그래프에서 구현하는 방법을 살펴보겠습니다.

3.1. 그래프 표현

그래프는 인접 리스트(Adjacency List) 방식으로 표현합니다. 인접 리스트는 각 노드에 연결된 노드 목록을 저장하여 효율적으로 연결 관계를 관리합니다.

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. DFS 구현 (재귀 방식)

public class DepthFirstSearch
{
    private HashSet<int> visited;

    public DepthFirstSearch()
    {
        visited = new HashSet<int>();
    }

    public void DFSRecursive(int node, Dictionary<int, List<int>> graph)
    {
        // 현재 노드를 방문 처리
        visited.Add(node);
        Console.WriteLine(node);

        // 현재 노드의 모든 인접 노드 탐색
        foreach (var neighbor in graph[node])
        {
            if (!visited.Contains(neighbor))
            {
                DFSRecursive(neighbor, graph);
            }
        }
    }
}

 

---

3.3. DFS 구현 (스택 방식)

public class DepthFirstSearch
{
    public void DFSUsingStack(int startNode, Dictionary<int, List<int>> graph)
    {
        var visited = new HashSet<int>();
        var stack = new Stack<int>();
        
        stack.Push(startNode);

        while (stack.Count > 0)
        {
            var node = stack.Pop();

            if (!visited.Contains(node))
            {
                visited.Add(node);
                Console.WriteLine(node);

                // 인접 노드를 스택에 추가
                foreach (var neighbor in graph[node])
                {
                    if (!visited.Contains(neighbor))
                    {
                        stack.Push(neighbor);
                    }
                }
            }
        }
    }
}

 

---

3.4. 실행 예시

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);

        // DFS 실행 (재귀)
        Console.WriteLine("DFS (Recursive):");
        var dfsRecursive = new DepthFirstSearch();
        dfsRecursive.DFSRecursive(1, graph.GetGraph());

        Console.WriteLine("\nDFS (Using Stack):");
        var dfsStack = new DepthFirstSearch();
        dfsStack.DFSUsingStack(1, graph.GetGraph());
    }
}

---

4. DFS의 응용 분야

1. 미로 탐색: 미로와 같은 경로 찾기 문제에서 유용합니다.
2. 순환 탐지: 그래프에서 사이클(순환)을 찾는 데 활용됩니다.
3. 강한 연결 요소: 그래프의 강한 연결 요소를 찾는 알고리즘(Kosaraju's Algorithm)에 사용됩니다.
4. 백트래킹: N-Queen, 미로 문제 등에서 DFS와 백트래킹 기법을 결합하여 해결합니다.

---

DFS는 그래프 탐색의 기본적인 알고리즘으로, 데이터 탐색 및 검색 문제를 해결하는 데 널리 사용됩니다. 재귀와 스택을 활용한 DFS 구현은 간단하지만, 그래프가 크거나 순환을 포함할 경우 방문 여부를 명확히 관리해야 합니다. DFS의 동작 원리와 구현을 이해하면 다양한 탐색 문제를 해결하는 데 큰 도움이 될 것입니다.