깊이 우선 탐색 DFS

 

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

 

DFS(깊이 우선 탐색)은 그래프나 트리 구조에서 한 정점으로부터 시작하여 깊이를 우선적으로 탐색하는 알고리즘입니다. 이 알고리즘은 주로 그래프의 모든 정점을 방문하거나 특정한 조건을 만족하는 정점을 찾는 데 사용됩니다.

 

DFS는 스택(Stack) 또는 재귀 함수를 통해 구현될 수 있습니다. 시작 정점에서 출발하여 다음 정점으로 이동하고, 그 다음 정점에서 또 다시 다음 정점으로 이동하는 식으로 깊이를 우선적으로 탐색합니다. 이러한 과정에서 방문한 정점은 방문했다는 표시를 하고, 이미 방문한 정점이라면 더 이상 탐색을 진행하지 않고 이전 단계로 되돌아갑니다.

 

DFS 코드 예시 (C#)

 

아래 코드는 그래프에서 깊이 우선 탐색을 수행하는 예시입니다. 각 정점을 리스트로 표현하고, 각 정점마다 연결된 정점을 추가하여 인접 리스트를 구성합니다. 그 후, 재귀적으로 깊이 우선 탐색을 수행합니다.

 

using System;
using System.Collections.Generic;

class Graph
{
    private int V; // 정점의 개수
    private List<int>[] adj; // 인접 리스트

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[V];
        for (int i = 0; i < V; ++i)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write(v + " ");

        foreach (int i in adj[v])
        {
            if (!visited[i])
            {
                Console.WriteLine();
                Console.WriteLine("DFS visiting vertex " + i + " from vertex " + v + ": ");
             	DFSUtil(i, visited);
            }
        }
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V];

        DFSUtil(v, visited);
    }
}

class Program
{
    public static void Main(string[] args)
    {
        Graph g = new Graph(4);

        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);

        Console.WriteLine("DFS starting from vertex 2:");
        g.DFS(2);
    }
}

 

위 코드를 실행한 결과는 다음과 같습니다.

 

DFS starting from vertex 2:
2 
DFS visiting vertex 0 from vertex 2: 
0 
DFS visiting vertex 1 from vertex 0: 
1 
DFS visiting vertex 3 from vertex 2: 
3

 

 

 

DFS 장단점

 

- 장점

• 간선의 개수에 상관없이 정점의 개수에 따라 탐색 시간이 결정되므로 깊이 우선 탐색은 너비 우선 탐색보다 메모리를 적게 사용합니다.
• 목표 정점이 깊은 단계에 있을 때 효율적으로 탐색합니다.

- 단점

• 최단 경로를 보장하지 않습니다.
• 무한 루프에 빠질 수 있습니다.

 

DFS 사용 사례

 

• 미로 찾기 : DFS는 미로를 탐색하고 최단 경로를 찾는 데 사용될 수 있습니다. 미로는 그래프로 표현될 수 있으며, 각 셀이 정점으로, 서로 인접한 셀들이 간선으로 연결됩니다. 시작 지점에서 출발하여 도착 지점까지 DFS를 사용하여 탐색하면, 최단 경로를 찾을 수 있습니다. DFS는 깊이 우선적으로 탐색하므로, 미로의 각 경로를 깊이 들어가면서 탐색하게 됩니다.
• 트리 순회 : 트리는 그래프의 일종으로, 부모와 자식 관계로 이루어진 자료 구조입니다. DFS는 트리를 순회하는 데 사용됩니다. 트리 순회에는 전위 순회(pre-order traversal), 중위 순회(in-order traversal), 후위 순회(post-order traversal)가 있습니다. DFS를 이용하여 트리를 순회할 때, 각 노드를 방문하는 순서에 따라 위의 순회 방법들을 구현할 수 있습니다.
• 위상 정렬 : 위상 정렬은 방향 그래프의 각 정점을 순서화하는 작업입니다. 이때, 그래프 내의 각 노드는 어떤 작업을 나타내며, 간선은 작업 간의 선후 관계를 나타냅니다. DFS는 위상 정렬을 수행하는데 사용될 수 있습니다. DFS를 통해 그래프를 탐색하면서 각 정점을 방문할 때, 그 정점의 모든 이웃을 먼저 방문하는 방식을 이용하여 위상 정렬을 수행할 수 있습니다. 위상 정렬을 통해 작업들을 순서대로 수행할 수 있는 순서를 찾을 수 있습니다.
  

 

DFS는 다양한 문제에서 활용되며, 특히 그래프와 관련된 문제에서 깊이 우선 탐색은 유용하게 사용됩니다.