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

개발_노트 2025. 2. 24. 14:57

📌 7. 깊이 우선 탐색(DFS, Depth First Search)

7.1 DFS 개념 및 원리

🔹 DFS(Depth First Search)란?

DFS(깊이 우선 탐색, Depth First Search)는 그래프에서 한 방향으로 최대한 깊이 탐색한 후, 더 이상 갈 곳이 없으면 되돌아가면서 탐색하는 방식입니다.
트리나 그래프 탐색에 사용되며, 미로 찾기, 경로 탐색, 위상 정렬 등에 유용합니다.

💡 DFS 탐색 원리:

시작 정점에서 가장 깊은 곳까지 탐색
더 이상 갈 곳이 없으면 되돌아가서 다른 경로 탐색
모든 정점을 방문할 때까지 반복

🔹 DFS의 동작 방식

예제 그래프가 다음과 같다고 가정하겠습니다.

  1 - 2
  |   |
  3 - 4 - 5

DFS 순서는 다음과 같습니다.
✔ 1 → 2 → 4 → 5 → 3 (깊이 우선 탐색)

🔹 DFS의 시간 복잡도

그래프 형태	시간 복잡도
인접 리스트(Adjacency List) 사용	O(V + E)
인접 행렬(Adjacency Matrix) 사용	O(V²)

V: 정점(Vertex) 개수, E: 간선(Edge) 개수
✔ 인접 리스트 방식이 일반적으로 더 효율적입니다.

7.2 재귀(Recursive) 방식과 스택(Stack) 기반 반복(Iterative) 방식 비교

DFS는 재귀 함수(Recursive)와 스택(Stack)을 이용한 반복(Iterative) 방식으로 구현할 수 있습니다.

방식	장점	단점
재귀(Recursive)	코드가 간결하고 이해하기 쉬움	재귀 호출이 깊어지면 스택 오버플로우 발생 가능
스택(Stack) 기반 반복(Iterative)	메모리 절약, 스택 오버플로우 방지	코드가 상대적으로 복잡함

7.3 그래프에서 DFS를 활용하는 예시

🔹 1) 미로 찾기 (Maze Solving)

DFS를 이용해 미로의 출구를 찾을 수 있음
방문한 경로를 추적하며 길을 탐색

🔹 2) 위상 정렬 (Topological Sorting)

방향 그래프(DAG)에서 작업의 순서를 정하는 알고리즘
DFS 후 역순으로 정점을 정렬하면 위상 정렬 결과가 나옴

🔍 실습: DFS 구현

1️⃣ 재귀 함수 기반 DFS 구현

#include <stdio.h>

#define V 5  // 정점 개수

// 그래프 인접 행렬
int graph[V][V] = {
    {0, 1, 1, 0, 0},
    {1, 0, 0, 1, 0},
    {1, 0, 0, 1, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 1, 1, 0}
};

int visited[V] = {0};  // 방문 여부 저장

// DFS 재귀 함수
void DFS_recursive(int node) {
    printf("%d ", node);
    visited[node] = 1; // 방문 표시

    for (int i = 0; i < V; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            DFS_recursive(i);
        }
    }
}

int main() {
    printf("DFS 탐색 순서 (재귀 방식): ");
    DFS_recursive(0); // 0번 정점부터 시작
    printf("\n");
    return 0;
}

📌 실행 결과

DFS 탐색 순서 (재귀 방식): 0 1 3 2 4

✔ 각 정점에서 연결된 가장 깊은 정점부터 탐색

2️⃣ 스택을 이용한 반복 DFS 구현

#include <stdio.h>
#include <stdlib.h>

#define V 5

// 그래프 인접 행렬
int graph[V][V] = {
    {0, 1, 1, 0, 0},
    {1, 0, 0, 1, 0},
    {1, 0, 0, 1, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 1, 1, 0}
};

// DFS 스택 기반 반복 구현
void DFS_iterative(int start) {
    int visited[V] = {0}; // 방문 여부 저장
    int stack[V];
    int top = -1; // 스택 포인터

    stack[++top] = start; // 시작 정점을 스택에 추가

    while (top >= 0) {
        int node = stack[top--]; // 스택에서 정점 꺼내기

        if (!visited[node]) {
            printf("%d ", node);
            visited[node] = 1;

            // 인접 정점을 스택에 추가 (큰 숫자부터 작은 숫자 순서로 추가)
            for (int i = V - 1; i >= 0; i--) {
                if (graph[node][i] == 1 && !visited[i]) {
                    stack[++top] = i;
                }
            }
        }
    }
}

int main() {
    printf("DFS 탐색 순서 (반복 스택 방식): ");
    DFS_iterative(0);
    printf("\n");
    return 0;
}

📌 실행 결과

DFS 탐색 순서 (반복 스택 방식): 0 2 4 3 1

✔ 스택을 사용하여 DFS를 구현하면 메모리 효율적으로 탐색 가능

3️⃣ 미로 탐색 알고리즘 적용

DFS를 사용하여 미로의 출구를 찾는 예제입니다.

#include <stdio.h>

#define N 5

// 미로 지도 (0: 길, 1: 벽)
int maze[N][N] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

// 방문 기록 배열
int visited[N][N] = {0};

// 방향 벡터 (상, 하, 좌, 우)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// DFS 탐색 함수
int DFS_maze(int x, int y) {
    if (x == N - 1 && y == N - 1) {
        printf("출구 도착!\n");
        return 1; // 출구 도착
    }

    visited[x][y] = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
            if (maze[nx][ny] == 0 && !visited[nx][ny]) {
                if (DFS_maze(nx, ny)) return 1;
            }
        }
    }

    return 0; // 길이 없음
}

int main() {
    if (DFS_maze(0, 0)) {
        printf("미로 탈출 성공!\n");
    } else {
        printf("출구에 도달할 수 없습니다.\n");
    }
    return 0;
}

📌 실행 결과

출구 도착!
미로 탈출 성공!

✔ DFS를 사용하여 미로 출구를 찾음

📌 마무리 및 정리

DFS는 그래프를 깊이 우선 탐색하는 방식
재귀 vs 스택 기반 반복 방식 비교
미로 찾기, 위상 정렬 등에 활용 가능