MENU
  1. ホーム
  2. C 언어
  3. C 언어로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 완벽 가이드

C 언어로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 완벽 가이드

C 언어

C 언어에서 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)은 그래프 탐색의 핵심적인 알고리즘으로, 다양한 문제 해결에 활용됩니다. 이 기사에서는 DFS와 BFS의 기본 개념, 구현 방법, 그리고 실제 응용 사례를 다뤄 C 언어 프로그래밍에서의 효율적인 활용법을 소개합니다. DFS는 깊이를 우선으로 탐색하는 방식이며, BFS는 너비를 우선으로 탐색하여 서로 다른 문제를 해결하는 데 적합합니다. 이 두 알고리즘을 배우고 활용하면 그래프 기반 문제를 효과적으로 다룰 수 있습니다.

목차

DFS와 BFS의 개념 및 차이점


깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)은 그래프 탐색에서 가장 널리 사용되는 두 가지 알고리즘입니다.

DFS의 개념


DFS는 그래프에서 한 경로를 따라 최대한 깊이 탐색한 후, 더 이상 탐색할 노드가 없을 때 이전 노드로 돌아오는 방식입니다. 주로 재귀나 스택을 사용하여 구현됩니다.

BFS의 개념


BFS는 그래프에서 시작 노드의 모든 인접 노드를 탐색한 후, 그다음 수준의 노드들을 탐색하는 방식입니다. 큐를 사용하여 구현하며, 주로 최단 경로 탐색에 적합합니다.

DFS와 BFS의 차이점

탐색 순서


DFS는 깊이를 우선으로 탐색하는 반면, BFS는 너비를 우선으로 탐색합니다.

사용 구조


DFS는 스택(재귀 포함)을 사용하고, BFS는 큐를 사용합니다.

적합한 문제


DFS는 모든 경로를 탐색하거나 특정 조건을 만족하는 경로를 찾을 때 유리하며, BFS는 최단 경로를 찾거나 수준별 탐색이 필요한 경우 적합합니다.

이 두 알고리즘은 문제에 따라 선택적으로 사용되며, 구현 방식의 차이를 이해하는 것이 중요합니다.

DFS 알고리즘의 작동 원리

DFS의 기본 작동 방식


DFS는 그래프에서 시작 노드에서 출발하여 가능한 깊이까지 탐색한 뒤, 더 이상 진행할 경로가 없으면 이전 노드로 되돌아가는 방식입니다.

  1. 노드 방문: 시작 노드에서 출발해 방문하지 않은 인접 노드를 탐색합니다.
  2. 경로 따라가기: 가능한 한 깊이 있는 경로를 따라가며 노드를 방문합니다.
  3. 백트래킹: 더 이상 방문할 노드가 없을 경우, 이전 노드로 돌아가 탐색을 이어갑니다.

DFS 구현의 핵심


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

1. 재귀를 사용한 DFS


재귀 호출을 통해 자동으로 스택 구조를 형성하여 깊이를 탐색합니다. 이 방식은 코드가 간결하지만, 재귀 호출로 인해 스택 오버플로우의 위험이 있습니다.

2. 스택을 사용한 DFS


명시적인 스택을 사용하여 재귀 없이 구현할 수 있습니다. 이 방식은 메모리 사용량을 명확히 관리할 수 있는 장점이 있습니다.

DFS의 주요 응용

  1. 경로 탐색: 그래프에서 특정 조건을 만족하는 경로를 찾습니다.
  2. 사이클 검출: 무향 그래프에서 사이클이 존재하는지 확인할 수 있습니다.
  3. 그래프 연결성 분석: 연결 요소를 탐색하여 그래프의 전체 구조를 이해합니다.

DFS의 예제 코드 구조

void DFS(int node, bool visited[], int graph[][MAX]) {
    visited[node] = true;
    printf("%d ", node);
    for (int i = 0; i < MAX; i++) {
        if (graph[node][i] && !visited[i]) {
            DFS(i, visited, graph);
        }
    }
}


위 코드는 재귀를 사용해 DFS를 구현한 기본적인 예제입니다. 입력으로 그래프와 방문 여부를 전달받아 각 노드를 깊이 우선으로 탐색합니다.

DFS는 탐색 대상이 많거나 깊이가 큰 경우 유용하게 사용되며, 효율적인 경로 탐색 및 분석에 필수적인 알고리즘입니다.

BFS 알고리즘의 작동 원리

BFS의 기본 작동 방식


BFS는 그래프에서 시작 노드의 모든 인접 노드를 탐색한 뒤, 그다음 수준(level)의 노드들을 순차적으로 탐색하는 알고리즘입니다.

  1. 노드 방문: 시작 노드를 큐에 추가하고 방문합니다.
  2. 큐 처리: 큐에서 노드를 꺼내 해당 노드의 인접 노드들을 순차적으로 방문하며 큐에 추가합니다.
  3. 레벨별 탐색: 큐가 비워질 때까지 위 과정을 반복하며 그래프를 레벨 단위로 탐색합니다.

BFS 구현의 핵심

1. 큐의 사용


BFS는 큐 자료구조를 활용해 탐색 순서를 제어합니다.

  • 큐의 enqueue: 새로운 노드를 큐에 추가합니다.
  • 큐의 dequeue: 큐에서 노드를 제거하며, 제거된 노드를 탐색합니다.

2. 방문 처리


이미 방문한 노드를 재방문하지 않도록 방문 여부를 기록합니다.

BFS의 주요 응용

  1. 최단 경로 탐색: 그래프에서 두 노드 사이의 최단 경로를 찾는 데 유용합니다(가중치 없는 그래프).
  2. 그래프 레벨 탐색: 트리나 그래프의 노드들을 계층적으로 탐색할 수 있습니다.
  3. 최소 스패닝 트리 생성: BFS를 활용하여 특정 문제를 단순화할 수 있습니다.

BFS의 예제 코드 구조

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

#define MAX 100

void BFS(int start, int graph[][MAX], bool visited[], int n) {
    int queue[MAX];
    int front = 0, rear = 0;

    queue[rear++] = start;
    visited[start] = true;

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);

        for (int i = 0; i < n; i++) {
            if (graph[node][i] && !visited[i]) {
                queue[rear++] = i;
                visited[i] = true;
            }
        }
    }
}


이 코드는 BFS를 구현한 기본 예제입니다. 큐를 사용해 그래프의 시작 노드에서 출발하여 레벨 단위로 모든 노드를 탐색합니다.

BFS의 특징

  • 그래프의 구조를 체계적으로 분석할 수 있습니다.
  • DFS와 달리 깊이에 상관없이 레벨 단위로 탐색을 진행합니다.
  • BFS는 구현이 비교적 간단하며, 메모리 사용량이 일정합니다.

BFS는 그래프의 레벨 구조를 확인하거나 최단 경로를 탐색할 때 매우 효과적인 알고리즘입니다.

C 언어로 DFS 구현하기

DFS 구현의 기본 구조


C 언어에서 DFS는 주로 재귀를 사용하여 구현합니다. 그래프를 배열 또는 인접 리스트로 표현하고, 방문 여부를 기록하는 배열을 통해 탐색 상태를 추적합니다.

DFS 구현 예제


다음은 DFS를 구현한 예제 코드입니다.

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

void DFS(int node, bool visited[], int graph[][MAX], int n) {
    visited[node] = true;
    printf("%d ", node);  // 방문한 노드 출력

    for (int i = 0; i < n; i++) {
        if (graph[node][i] && !visited[i]) {  // 인접 노드 중 방문하지 않은 노드 탐색
            DFS(i, visited, graph, n);
        }
    }
}

int main() {
    int graph[MAX][MAX] = {0};
    bool visited[MAX] = {false};
    int n, edges;

    printf("노드 수와 간선 수를 입력하세요: ");
    scanf("%d %d", &n, &edges);

    printf("간선을 입력하세요 (노드 번호는 0부터 시작):\n");
    for (int i = 0; i < edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;  // 무방향 그래프일 경우 graph[v][u] = 1; 추가
    }

    printf("DFS 탐색 결과: ");
    DFS(0, visited, graph, n);  // 0번 노드에서 시작
    return 0;
}

코드 설명

  1. 입력 처리: 그래프의 노드 수와 간선을 입력받아 인접 행렬을 초기화합니다.
  2. 방문 처리: visited 배열로 각 노드의 방문 여부를 추적합니다.
  3. 재귀 호출: DFS 함수는 재귀적으로 호출되어 인접 노드를 탐색합니다.

DFS 코드의 특징

  • 재귀 사용: 간결하고 직관적인 구현이 가능하지만, 깊이가 깊어질 경우 스택 오버플로우의 위험이 있습니다.
  • 효율성: 그래프가 희소(sparse) 그래프일 경우 효율적으로 동작합니다.

DFS 테스트 예시


입력:

노드 수와 간선 수를 입력하세요: 4 4  
간선을 입력하세요 (노드 번호는 0부터 시작):  
0 1  
0 2  
1 2  
2 3


출력:

DFS 탐색 결과: 0 1 2 3

응용


DFS는 특정 경로 찾기, 사이클 검출, 연결 요소 분석 등의 문제를 해결하는 데 유용합니다. 이를 통해 그래프 관련 문제의 기본기를 다질 수 있습니다.

C 언어로 BFS 구현하기

BFS 구현의 기본 구조


BFS는 큐를 이용하여 구현됩니다. 시작 노드를 큐에 추가한 뒤, 큐에서 노드를 하나씩 꺼내며 그 노드와 연결된 인접 노드들을 탐색합니다. 방문 여부를 기록하는 배열을 활용하여 이미 방문한 노드는 재방문하지 않도록 처리합니다.

BFS 구현 예제


다음은 BFS를 구현한 예제 코드입니다.

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

void BFS(int start, int graph[][MAX], bool visited[], int n) {
    int queue[MAX];
    int front = 0, rear = 0;

    // 시작 노드 방문 및 큐에 추가
    queue[rear++] = start;
    visited[start] = true;

    while (front < rear) {
        int node = queue[front++];  // 큐에서 노드 꺼내기
        printf("%d ", node);       // 방문한 노드 출력

        for (int i = 0; i < n; i++) {
            if (graph[node][i] && !visited[i]) {  // 인접 노드 중 방문하지 않은 노드 탐색
                queue[rear++] = i;  // 큐에 추가
                visited[i] = true;  // 방문 처리
            }
        }
    }
}

int main() {
    int graph[MAX][MAX] = {0};
    bool visited[MAX] = {false};
    int n, edges;

    printf("노드 수와 간선 수를 입력하세요: ");
    scanf("%d %d", &n, &edges);

    printf("간선을 입력하세요 (노드 번호는 0부터 시작):\n");
    for (int i = 0; i < edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;  // 무방향 그래프일 경우 graph[v][u] = 1; 추가
    }

    printf("BFS 탐색 결과: ");
    BFS(0, graph, visited, n);  // 0번 노드에서 시작
    return 0;
}

코드 설명

  1. 큐 초기화: queue 배열로 노드를 저장하며, front와 rear로 큐의 상태를 관리합니다.
  2. 방문 처리: visited 배열로 각 노드의 방문 여부를 추적합니다.
  3. 큐 기반 탐색: 큐에서 노드를 꺼내 인접 노드를 큐에 추가하며 탐색을 진행합니다.

BFS 코드의 특징

  • 레벨 단위 탐색: 노드를 탐색할 때 레벨 순서로 진행됩니다.
  • 큐 사용: BFS는 큐를 사용하여 구현되며, 선입선출(FIFO) 원칙을 따릅니다.

BFS 테스트 예시


입력:

노드 수와 간선 수를 입력하세요: 4 4  
간선을 입력하세요 (노드 번호는 0부터 시작):  
0 1  
0 2  
1 2  
2 3


출력:

BFS 탐색 결과: 0 1 2 3

응용


BFS는 최단 경로 탐색, 그래프의 모든 연결 요소 탐색, 그래프에서 특정 레벨의 노드 찾기 등 다양한 문제를 해결하는 데 사용됩니다. 이 알고리즘은 그래프의 구조를 효율적으로 분석할 수 있는 강력한 도구입니다.

DFS와 BFS의 응용 사례

DFS의 주요 응용

1. 경로 탐색


DFS는 그래프 내의 특정 경로를 탐색하거나 경로의 존재 여부를 확인하는 데 유용합니다. 예를 들어, 미로 탐색 문제에서 출발점에서 목표 지점까지의 경로를 찾는 데 사용됩니다.

  • 예시: 미로에서 출발 지점에서 목표 지점까지의 모든 가능한 경로를 탐색합니다.

2. 사이클 검출


DFS는 방향성 그래프에서 사이클이 존재하는지 확인하는 데 사용됩니다. 방문 중인 노드가 다시 방문되면 사이클이 존재한다고 판단합니다.

  • 예시: 작업 스케줄링 그래프에서 순환 종속성을 확인합니다.

3. 연결 요소 탐색


DFS는 그래프의 연결 요소를 탐색하여 그래프의 구조적 정보를 제공합니다.

  • 예시: 소셜 네트워크에서 연결된 그룹을 식별합니다.

BFS의 주요 응용

1. 최단 경로 탐색


BFS는 가중치가 없는 그래프에서 두 노드 간의 최단 경로를 찾는 데 적합합니다.

  • 예시: 지하철 네트워크에서 두 역 간의 최소 환승 경로를 찾습니다.

2. 수준 탐색


BFS는 노드를 레벨 단위로 탐색하기 때문에 그래프의 특정 수준(level)에 존재하는 노드를 탐색하는 데 유용합니다.

  • 예시: 조직도에서 특정 직급의 직원을 찾습니다.

3. 그래프 구성 분석


BFS는 그래프의 전체적인 구조를 분석하거나 특정 노드와의 관계를 확인하는 데 효과적입니다.

  • 예시: 전염병 전파 모델에서 감염이 퍼지는 과정을 시뮬레이션합니다.

DFS와 BFS의 실제 활용 예시

  • 웹 크롤러: DFS는 웹 페이지의 링크를 따라 깊게 탐색하며 정보를 수집하는 데 사용됩니다.
  • 게임 탐색 알고리즘: BFS는 퍼즐 게임에서 최소 이동 횟수를 찾는 데 사용됩니다.
  • 네트워크 분석: DFS와 BFS 모두 소셜 네트워크에서 사용자 간의 관계를 분석하거나 연결된 클러스터를 찾는 데 활용됩니다.

DFS와 BFS는 다양한 문제에서 서로 보완적인 역할을 하며, 상황에 따라 적합한 알고리즘을 선택하는 것이 중요합니다.

DFS와 BFS를 선택하는 기준

DFS를 선택해야 하는 경우

1. 깊이 우선의 탐색이 필요한 경우


DFS는 특정 경로를 따라 깊이 탐색하며, 모든 가능한 경로를 탐색하거나 특정 조건을 만족하는 경로를 찾는 데 적합합니다.

  • 예시: 퍼즐 게임에서 가능한 모든 경로를 탐색하여 해결 방안을 찾는 경우.

2. 메모리 사용량이 제한적인 경우


DFS는 스택(또는 재귀 호출)을 사용하기 때문에 BFS보다 메모리를 적게 사용하는 경향이 있습니다.

  • 예시: 큰 그래프에서 메모리 제한이 있는 시스템.

3. 백트래킹이 필요한 문제


DFS는 백트래킹과 자연스럽게 결합되므로 최적의 결과를 찾기 위해 탐색을 되돌릴 수 있는 문제에 적합합니다.

  • 예시: 미로 탐색, 순열 및 조합 생성 문제.

BFS를 선택해야 하는 경우

1. 최단 경로가 필요한 경우


BFS는 레벨 단위로 탐색하기 때문에 가중치 없는 그래프에서 두 노드 간의 최단 경로를 찾는 데 적합합니다.

  • 예시: 지도에서 두 지점 간의 최소 이동 경로 찾기.

2. 레벨 기반 탐색이 필요한 경우


BFS는 노드를 레벨 단위로 탐색하므로 특정 수준(level)에 존재하는 노드들을 찾는 데 적합합니다.

  • 예시: 조직도에서 특정 직급의 직원을 탐색하는 경우.

3. 대규모 그래프를 처리하는 경우


BFS는 그래프의 노드를 넓게 탐색하므로 구조적인 이해를 위해 더 적합할 수 있습니다.

  • 예시: 네트워크 분석에서 감염 전파 또는 연결 상태를 확인하는 경우.

DFS와 BFS 비교

기준DFSBFS
탐색 방식깊이를 우선으로 탐색너비를 우선으로 탐색
사용 구조스택 (재귀 포함)큐
적합한 문제경로 탐색, 백트래킹, 사이클 검출최단 경로, 레벨 탐색
메모리 사용상대적으로 적음상대적으로 많음

결론


DFS와 BFS는 그래프 탐색에서 각각의 강점이 있습니다. 깊이를 중점으로 한 탐색이 필요하거나 경로를 완전히 탐색해야 하는 경우 DFS를 사용하고, 최단 경로를 찾거나 그래프의 레벨 구조를 분석해야 할 때 BFS를 선택합니다. 문제의 성격과 요구사항에 따라 적절한 알고리즘을 활용하는 것이 중요합니다.

연습 문제와 해결 방법

연습 문제 1: 그래프에서 연결 요소 찾기 (DFS 활용)


문제:
방향성이 없는 그래프가 주어졌을 때, 그래프의 연결 요소의 개수를 구하세요.

입력 예시:

노드 수와 간선 수를 입력하세요: 6 4  
간선을 입력하세요 (노드 번호는 0부터 시작):  
0 1  
2 3  
4 5

출력 예시:

연결 요소의 개수: 3

해결 방법:
DFS를 사용하여 방문하지 않은 모든 노드에서 탐색을 시작하고, 각 탐색이 새로운 연결 요소를 나타냅니다.

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

void DFS(int node, bool visited[], int graph[][MAX], int n) {
    visited[node] = true;
    for (int i = 0; i < n; i++) {
        if (graph[node][i] && !visited[i]) {
            DFS(i, visited, graph, n);
        }
    }
}

int main() {
    int graph[MAX][MAX] = {0};
    bool visited[MAX] = {false};
    int n, edges, components = 0;

    printf("노드 수와 간선 수를 입력하세요: ");
    scanf("%d %d", &n, &edges);

    printf("간선을 입력하세요 (노드 번호는 0부터 시작):\n");
    for (int i = 0; i < edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1;  // 무방향 그래프
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS(i, visited, graph, n);
            components++;
        }
    }

    printf("연결 요소의 개수: %d\n", components);
    return 0;
}

연습 문제 2: 최단 경로 찾기 (BFS 활용)


문제:
가중치 없는 방향성 그래프가 주어졌을 때, 주어진 시작 노드에서 모든 다른 노드까지의 최단 거리를 구하세요.

입력 예시:

노드 수와 간선 수를 입력하세요: 4 4  
간선을 입력하세요 (노드 번호는 0부터 시작):  
0 1  
0 2  
1 2  
2 3  
시작 노드: 0

출력 예시:

노드 0에서의 최단 거리:  
0: 0  
1: 1  
2: 1  
3: 2

해결 방법:
BFS를 사용하여 시작 노드에서 각 노드까지의 거리를 계산합니다.

#include <stdio.h>
#include <stdbool.h>

#define MAX 100
#define INF 1000000

void BFS(int start, int graph[][MAX], int distance[], int n) {
    int queue[MAX];
    int front = 0, rear = 0;

    queue[rear++] = start;
    distance[start] = 0;

    while (front < rear) {
        int node = queue[front++];
        for (int i = 0; i < n; i++) {
            if (graph[node][i] && distance[i] == INF) {
                queue[rear++] = i;
                distance[i] = distance[node] + 1;
            }
        }
    }
}

int main() {
    int graph[MAX][MAX] = {0};
    int distance[MAX];
    int n, edges, start;

    printf("노드 수와 간선 수를 입력하세요: ");
    scanf("%d %d", &n, &edges);

    printf("간선을 입력하세요 (노드 번호는 0부터 시작):\n");
    for (int i = 0; i < edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1;  // 무방향 그래프
    }

    printf("시작 노드: ");
    scanf("%d", &start);

    for (int i = 0; i < n; i++) {
        distance[i] = INF;
    }

    BFS(start, graph, distance, n);

    printf("노드 %d에서의 최단 거리:\n", start);
    for (int i = 0; i < n; i++) {
        printf("%d: %d\n", i, distance[i]);
    }

    return 0;
}

연습 문제를 통한 이해 심화


위 연습 문제를 풀어 보며 DFS와 BFS의 특징과 구현 방법을 실습해 보세요. 실제 문제에 적용하여 각각의 알고리즘이 어떤 상황에서 유리한지 직접 체험할 수 있습니다.

요약


DFS와 BFS는 그래프 탐색의 핵심 알고리즘으로, 각각 깊이와 너비를 우선으로 탐색하는 특성을 가집니다. DFS는 경로 탐색, 사이클 검출, 연결 요소 분석 등에서 유용하며, BFS는 최단 경로 탐색과 레벨 기반 탐색에 적합합니다. C 언어로 두 알고리즘을 구현하는 방법과 주요 응용 사례, 연습 문제를 통해 이들의 활용 방식을 익힐 수 있었습니다. 적합한 알고리즘을 선택하여 다양한 그래프 기반 문제를 효과적으로 해결할 수 있습니다.

C 언어
BFS C 언어 DFS 알고리즘
목차