깊이 우선 탐색 ( DFS )

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

자료구조 내에서 찾고자 하는 데이터를 찾는 방식은 여러 알고리즘과 기법이 존재한다.

깊이 우선 탐색은 그래프 탐색 알고리즘 중 하나이다.

한 방향으로 갈 수 있는 곳까지 계속 탐색한 다음 , 막히면 다시 이전 분기점으로 돌아와 다른 경로를 탐색한다.

이런 방식은 트리 구조 탐색 뿐만 아니라 , 미로 찾기 , 경로 탐색 , 사이클 검사 등 다양한 문제에 사용된다.

 

현재 정점에서 탐색을 시작해서 갈 수 있는 곳까지 계속 내려가며 탐색한다.
더 이상 갈 곳이 없으면 되돌아가 다른 경로로 탐색을 이어나간다.

한 경로를 끝까지 파고들어가기 때문에 "깊이 우선" 이라는 이름이 붙었다.

탐색의 흐름은 재귀함수 호출 또는 스택 자료구조를 이용해 구현할 수 있다.

둘 다 같은 방식으로 탐색을 수행하지만

• 재귀는 호출 스택을 활용
• 반복문은 명시적인 스택 사용

이라는 차이점이 있다.

 

 

의사코드 ( Pseudocode )

▼ 재귀 방식

DFS(graph, node, visited)
    visited[node]를 true로 표시

    for (node와 연결된 모든 인접 정점 next에 대해 반복)
        if (visited[next]가 false라면)
            DFS(graph, next, visited)

• visited 배열은 각 정점을 한 번만 방문하도록 한다
• 재귀 호출을 통해 연결된 모든 정점을 자동으로 순회하게 된다

 

 

▼ 스택 사용 방식 ( 반복문 기반 )

DFS(graph, start)
    visited 배열 초기화
    스택에 start 정점을 push

    while (스택이 비어 있지 않음)
        현재 정점 = 스택에서 pop
        if (현재 정점을 방문한 적이 없다면)
            visited[현재 정점] = true

            현재 정점과 연결된 모든 인접 정점을
            스택에 push (아직 방문하지 않은 것만)

• 스택을 명시적으로 사용해서 DFS 흐름을 재현한다
• 이 방식은 재귀 호출을 사용하지 않기 때문에 호출 스택 제한 없이 더 큰 그래프도 탐색할 수 있다.

 

 

예시 코드 ( 인접 리스트 , 재귀 DFS )

그래프를 List<int>[ ] 로 표현

using System;
using System.Collections.Generic;

class DFSExample
{
    static List<int>[] graph;
    static bool[] visited;

    static void Main()
    {
        int n = 5; // 정점 개수 (0 ~ 4)
        graph = new List<int>[n];
        visited = new bool[n];

        for (int i = 0; i < n; i++)
        {
            graph[i] = new List<int>();
        }

        // 무방향 그래프 예시
        AddEdge(0, 1);
        AddEdge(0, 2);
        AddEdge(1, 3);
        AddEdge(2, 4);

        DFS(0); // 0부터 시작
    }

    static void AddEdge(int a, int b)
    {
        graph[a].Add(b);
        graph[b].Add(a);
    }

    static void DFS(int node)
    {
        visited[node] = true;
        Console.WriteLine($"Visit: {node}");

        foreach (int next in graph[node])
        {
            if (!visited[next])
            {
                DFS(next);
            }
        }
    }
}

 

 

DFS 시간 복잡도

• 정점 수 : V
• 간선 수 : E

자료구조	시간 복잡도	설명
인접 리스트	O( V + E )	정점 ( V )과 간선 ( E )을 한 번씩 방문한다
인접 행렬	O( V² )	모든 정점 간 연결 여부 확인이 필요하다
공간 복잡도	O( V )	방문 체크 배열 , 재귀 호출 스택 또는 명시적으로 스택 사용

• 실제 성능은 그래프 표현 방식에 따라 달라진다.

 

 

 

정리

• 한 길로 깊게 들어가다가 막히면 돌아와서 다른 길로 가는 탐색
• 재귀 or 스택으로 구현한다
• 그래프 / 트리 탐색 , 경로 탐색 , 백트래킹에 자주 사용한다