MENU
  1. ホーム
  2. C 언어
  3. C언어로 깊이 우선 탐색(DFS) 구현 방법 완벽 가이드

C언어로 깊이 우선 탐색(DFS) 구현 방법 완벽 가이드

C 언어

깊이 우선 탐색(DFS)은 컴퓨터 과학에서 그래프 탐색 및 순회에 널리 사용되는 알고리즘입니다. DFS는 각 정점을 깊이 우선으로 탐색하며, 재귀 호출이나 스택을 활용해 구현됩니다. 본 기사에서는 C언어로 DFS를 구현하는 방법을 살펴보고, 알고리즘의 작동 원리와 활용 사례를 다룹니다. 이를 통해 독자들은 DFS 알고리즘을 이해하고 직접 구현할 수 있는 능력을 갖추게 될 것입니다.

목차

DFS의 개념 및 용도


깊이 우선 탐색(DFS, Depth-First Search)은 그래프나 트리에서의 탐색 알고리즘으로, 가능한 깊은 경로를 우선적으로 탐색하는 것이 특징입니다. DFS는 한 경로를 끝까지 탐색한 뒤, 더 이상 탐색할 노드가 없을 경우에만 다른 경로로 이동합니다.

DFS의 주요 용도


DFS는 다음과 같은 경우에 유용하게 사용됩니다.

  • 경로 탐색: 두 정점 간의 경로가 존재하는지 확인
  • 사이클 검출: 그래프에서 사이클이 존재하는지 판별
  • 위상 정렬: DAG(유향 비순환 그래프)의 정점 순서 결정
  • 강결합 컴포넌트 탐색: 그래프 내의 강결합 컴포넌트 찾기

DFS의 특징

  • DFS는 방문 여부를 확인하여 불필요한 탐색을 방지합니다.
  • DFS는 재귀적으로 구현하거나 스택 자료구조를 활용해 비재귀적으로 구현할 수 있습니다.
  • 시간 복잡도는 그래프의 정점 수(V)와 간선 수(E)에 따라 O(V + E)입니다.

DFS는 알고리즘의 심층적인 이해와 다양한 문제 해결에 핵심적인 도구로 활용됩니다.

DFS를 구현하기 위한 그래프 표현 방식


DFS를 구현하려면 그래프를 적절히 표현하는 방법을 선택해야 합니다. 그래프 표현 방식에 따라 알고리즘의 효율성과 구현의 복잡성이 달라집니다.

인접 행렬


인접 행렬은 정점 간의 연결 관계를 이차원 배열로 표현합니다.

  • 구조: graph[i][j] = 1이면 정점 i와 정점 j가 연결됨을 의미합니다.
  • 장점: 구현이 간단하며, 간선 존재 여부를 O(1) 시간에 확인 가능
  • 단점: 메모리 사용량이 많아, 희소 그래프에는 비효율적
#define MAX 100
int graph[MAX][MAX] = {0}; // 그래프 초기화

인접 리스트


인접 리스트는 각 정점에 연결된 다른 정점들을 리스트로 표현합니다.

  • 구조: 배열의 각 인덱스가 정점을 나타내고, 해당 인덱스의 리스트가 연결된 정점을 나타냅니다.
  • 장점: 메모리를 절약할 수 있어, 희소 그래프에 적합
  • 단점: 특정 간선의 존재 여부를 확인하는 데 O(k)의 시간이 소요(k는 연결된 정점의 수)
#include <stdio.h>
#include <stdlib.h>
#define MAX 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX]; // 인접 리스트

간선 리스트


간선 리스트는 간선을 (정점1, 정점2) 형태로 저장합니다.

  • 구조: 배열 또는 리스트에 모든 간선을 저장
  • 장점: 그래프 데이터 저장이 간단하고, 메모리 효율적
  • 단점: 간선 탐색이 비효율적이며, DFS 구현에는 부적합
typedef struct Edge {
    int src, dest;
} Edge;

Edge edges[MAX];

그래프 표현 방식 선택 기준

  • 그래프 크기가 작거나 밀집된 그래프: 인접 행렬
  • 희소 그래프: 인접 리스트
  • 단순한 그래프 데이터 저장: 간선 리스트

DFS 구현 시에는 대체로 인접 리스트 방식이 가장 널리 사용됩니다. 이는 메모리와 탐색 성능 측면에서 균형 잡힌 선택이기 때문입니다.

DFS 알고리즘의 동작 원리


깊이 우선 탐색(DFS) 알고리즘은 그래프 탐색 시 한 경로를 끝까지 탐색한 뒤, 탐색하지 않은 경로로 되돌아가 다른 경로를 탐색하는 방식으로 작동합니다.

DFS의 동작 과정

  1. 시작 정점 선택: 탐색을 시작할 정점을 선택합니다.
  2. 정점 방문 및 기록: 현재 정점을 방문하고, 방문 여부를 기록합니다.
  3. 인접 정점 탐색: 현재 정점에 인접한 정점 중 방문하지 않은 정점을 선택해 탐색을 이어갑니다.
  4. 백트래킹: 더 이상 방문할 정점이 없으면 이전 정점으로 돌아갑니다.
  5. 모든 정점 탐색 완료: 그래프의 모든 정점을 탐색할 때까지 위 과정을 반복합니다.

DFS 알고리즘의 특징

  • 재귀적 접근: DFS는 재귀 호출로 자연스럽게 구현할 수 있습니다.
  • 스택 사용: 재귀를 사용하지 않을 경우 명시적인 스택 자료구조를 활용합니다.
  • 방문 여부 체크: 이미 방문한 정점을 다시 방문하지 않도록 방문 배열을 사용합니다.

DFS의 의사 코드

재귀적 구현:

void DFS(int vertex) {
    visited[vertex] = 1; // 현재 정점 방문 표시
    printf("%d ", vertex); // 정점 출력

    for (int i = 0; i < numVertices; i++) {
        if (graph[vertex][i] == 1 && !visited[i]) { // 연결된 정점 중 미방문 정점 탐색
            DFS(i);
        }
    }
}

스택을 사용한 비재귀적 구현:

void DFS_Iterative(int start) {
    Stack stack = createStack(); // 스택 초기화
    push(stack, start);

    while (!isEmpty(stack)) {
        int vertex = pop(stack);

        if (!visited[vertex]) {
            visited[vertex] = 1; // 방문 표시
            printf("%d ", vertex);

            for (int i = numVertices - 1; i >= 0; i--) { // 인접 정점 스택에 추가
                if (graph[vertex][i] == 1 && !visited[i]) {
                    push(stack, i);
                }
            }
        }
    }
}

DFS 동작 예시


주어진 그래프:

0 - 1 - 2  
|     |  
3     4
  • 시작 정점: 0
  • 탐색 순서: 0 → 1 → 4 → 2 → 3

DFS는 모든 정점을 깊이 우선으로 탐색하며, 이를 통해 그래프 탐색, 경로 발견, 트리 구조 탐색 등 다양한 문제를 해결합니다.

C언어로 DFS 구현하기


C언어로 깊이 우선 탐색(DFS)을 구현하려면 그래프를 표현하는 방식과 DFS 알고리즘을 결합해야 합니다. 가장 흔히 사용하는 인접 리스트 방식을 기반으로 재귀적 DFS 구현 예제를 살펴보겠습니다.

그래프 초기화


그래프는 정점과 간선으로 구성되며, 인접 리스트를 사용하여 표현합니다.

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

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX_VERTICES];
int visited[MAX_VERTICES];

void addEdge(int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = adjList[src];
    adjList[src] = newNode;

    // 무방향 그래프의 경우 반대 방향도 추가
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = adjList[dest];
    adjList[dest] = newNode;
}

DFS 함수 구현


재귀를 사용하여 DFS 알고리즘을 구현합니다.

void DFS(int vertex) {
    visited[vertex] = 1; // 현재 정점 방문 표시
    printf("%d ", vertex); // 정점 출력

    Node* temp = adjList[vertex];
    while (temp != NULL) {
        if (!visited[temp->vertex]) {
            DFS(temp->vertex); // 인접 정점으로 재귀 호출
        }
        temp = temp->next;
    }
}

메인 함수


그래프를 초기화하고 DFS를 실행합니다.

int main() {
    int numVertices = 5;

    // 인접 리스트 초기화
    for (int i = 0; i < numVertices; i++) {
        adjList[i] = NULL;
        visited[i] = 0;
    }

    // 그래프에 간선 추가
    addEdge(0, 1);
    addEdge(0, 3);
    addEdge(1, 2);
    addEdge(1, 4);
    addEdge(2, 4);

    printf("DFS Traversal starting from vertex 0:\n");
    DFS(0);

    return 0;
}

출력 결과


주어진 그래프에서 시작 정점이 0일 때의 출력 결과:

DFS Traversal starting from vertex 0:  
0 1 2 4 3

코드 설명

  1. 그래프 생성: addEdge 함수로 정점 간의 연결을 생성합니다.
  2. DFS 탐색: DFS 함수는 현재 정점을 방문 처리하고, 연결된 모든 미방문 정점으로 재귀 호출합니다.
  3. 방문 여부 관리: visited 배열로 중복 방문을 방지합니다.

장점

  • 인접 리스트를 사용하여 메모리 효율적으로 구현
  • 재귀를 통해 간결한 코드 작성

이 구현은 무방향 그래프를 기반으로 하며, 방향 그래프나 가중치가 있는 그래프에도 응용 가능합니다.

DFS 구현 시 고려해야 할 주요 요소


깊이 우선 탐색(DFS) 구현에서 주의해야 할 몇 가지 중요한 사항을 살펴봅니다. 이러한 요소를 잘 관리하면 알고리즘의 성능과 안정성을 향상시킬 수 있습니다.

1. 스택 오버플로 방지


DFS는 재귀 호출을 사용하기 때문에 재귀 깊이가 너무 깊어지면 스택 오버플로가 발생할 수 있습니다.

  • 해결 방법:
  • 입력 데이터가 큰 경우, 재귀 대신 명시적인 스택을 사용한 비재귀 DFS를 구현합니다.
  • 최대 재귀 깊이를 제한하거나 재귀 호출을 적절히 최적화합니다.

2. 방문 여부 체크


DFS는 그래프 내의 정점을 중복 방문하지 않아야 하므로, 방문 여부를 확인하는 배열을 사용하는 것이 중요합니다.

  • 예제:
int visited[MAX_VERTICES] = {0}; // 방문 여부 배열
  • 주의사항: 방문 배열을 초기화하지 않으면, 예상치 못한 오류가 발생할 수 있습니다.

3. 메모리 관리


C언어에서는 동적 메모리 할당을 사용하는 경우, 메모리 관리를 철저히 해야 합니다.

  • 해결 방법: DFS 탐색 후 free() 함수를 호출하여 동적 할당된 메모리를 해제합니다.
Node* temp = adjList[vertex];
while (temp != NULL) {
    Node* toFree = temp;
    temp = temp->next;
    free(toFree);
}

4. 그래프 표현 방식 선택


그래프의 크기와 밀도에 따라 적합한 표현 방식을 선택해야 합니다.

  • 밀집 그래프: 인접 행렬
  • 희소 그래프: 인접 리스트

5. 입력 데이터 처리


그래프를 정의하는 간선 정보가 파일이나 사용자 입력으로 주어지는 경우, 입력 데이터를 정확히 파싱해야 합니다.

  • 예제:
scanf("%d %d", &src, &dest);
addEdge(src, dest);

6. 방향 그래프와 무방향 그래프 처리

  • 무방향 그래프: 간선을 양방향으로 추가
  • 방향 그래프: 간선을 한 방향으로만 추가

7. DFS 종료 조건


DFS 탐색의 종료 조건을 명확히 설정해야 합니다.

  • 연결된 모든 정점을 탐색: 모든 인접 정점을 방문할 때까지 탐색
  • 특정 조건 탐색 종료: 예를 들어, 목표 정점을 찾으면 탐색을 종료

8. 시간 복잡도 최적화


DFS의 시간 복잡도는 O(V + E)로, 정점 수(V)와 간선 수(E)에 비례합니다. 적절한 그래프 표현 방식을 선택하면 성능을 최적화할 수 있습니다.

예시 코드


스택을 사용하여 재귀 없이 DFS를 구현하면 스택 오버플로를 방지할 수 있습니다.

void DFS_Iterative(int start) {
    Stack stack = createStack();
    push(stack, start);

    while (!isEmpty(stack)) {
        int vertex = pop(stack);

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

            Node* temp = adjList[vertex];
            while (temp != NULL) {
                if (!visited[temp->vertex]) {
                    push(stack, temp->vertex);
                }
                temp = temp->next;
            }
        }
    }
}

이와 같은 고려 사항을 바탕으로 DFS를 구현하면 메모리와 성능 문제를 최소화하고 안정적인 알고리즘을 만들 수 있습니다.

DFS 활용 예제


깊이 우선 탐색(DFS)은 다양한 문제를 해결하는 데 사용됩니다. 아래에서는 DFS를 활용한 두 가지 대표적인 문제와 관련 코드를 제시합니다.

1. 그래프에서 경로 존재 여부 확인


주어진 두 정점 간에 경로가 존재하는지 확인하는 문제입니다.

문제 설명

  • 입력: 그래프와 시작 정점, 목표 정점
  • 출력: 두 정점 간 경로가 존재하면 YES, 없으면 NO

코드 구현

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

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX_VERTICES];
int visited[MAX_VERTICES] = {0};
int found = 0;

void addEdge(int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = adjList[src];
    adjList[src] = newNode;
}

void DFS_FindPath(int vertex, int target) {
    if (vertex == target) {
        found = 1;
        return;
    }
    visited[vertex] = 1;

    Node* temp = adjList[vertex];
    while (temp != NULL && !found) {
        if (!visited[temp->vertex]) {
            DFS_FindPath(temp->vertex, target);
        }
        temp = temp->next;
    }
}

int main() {
    int numVertices = 5;
    for (int i = 0; i < numVertices; i++) {
        adjList[i] = NULL;
    }

    addEdge(0, 1);
    addEdge(0, 3);
    addEdge(1, 2);
    addEdge(1, 4);

    int start = 0, target = 4;
    DFS_FindPath(start, target);

    if (found) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }

    return 0;
}

출력 결과

YES

2. 연결 요소의 개수 계산


그래프의 연결 요소(connected components) 개수를 구하는 문제입니다.

문제 설명

  • 입력: 그래프
  • 출력: 연결 요소의 개수

코드 구현

int connectedComponents = 0;

void DFS_Connected(int vertex) {
    visited[vertex] = 1;
    Node* temp = adjList[vertex];
    while (temp != NULL) {
        if (!visited[temp->vertex]) {
            DFS_Connected(temp->vertex);
        }
        temp = temp->next;
    }
}

int main() {
    int numVertices = 6;
    for (int i = 0; i < numVertices; i++) {
        adjList[i] = NULL;
        visited[i] = 0;
    }

    addEdge(0, 1);
    addEdge(2, 3);
    addEdge(4, 5);

    for (int i = 0; i < numVertices; i++) {
        if (!visited[i]) {
            connectedComponents++;
            DFS_Connected(i);
        }
    }

    printf("Number of connected components: %d\n", connectedComponents);
    return 0;
}

출력 결과

Number of connected components: 3

DFS 활용 요약

  1. 경로 탐색: 두 정점 간의 연결 여부를 확인
  2. 연결 요소 계산: 그래프 내의 독립된 서브그래프 개수 확인
  3. 사이클 탐지: 그래프에 사이클이 존재하는지 확인
  4. 트리 구조 탐색: 트리 순회 및 분석

DFS는 위와 같은 문제를 해결하며, 다양한 그래프 탐색 알고리즘의 기반으로 활용됩니다.

요약


본 기사에서는 깊이 우선 탐색(DFS)의 개념, 구현 방법, 그리고 활용 사례를 C언어를 기반으로 상세히 살펴보았습니다. DFS는 그래프 탐색에서 매우 유용한 알고리즘으로, 재귀적 접근 방식과 스택 기반 구현 방법을 모두 지원합니다.

DFS를 구현할 때는 그래프 표현 방식의 선택, 방문 여부 관리, 메모리 최적화와 같은 요소를 고려해야 합니다. 이를 통해 경로 탐색, 연결 요소 계산, 사이클 탐지 등 다양한 문제를 효과적으로 해결할 수 있습니다.

DFS는 컴퓨터 과학 전반에서 기본적이고 필수적인 도구로, 효율적인 알고리즘 설계에 중요한 역할을 합니다.

C 언어
C언어 DFS 깊이 우선 탐색
목차