MENU
  1. ホーム
  2. C 언어
  3. C 언어로 구현하는 그래프 탐색 알고리즘: DFS와 BFS의 비교

C 언어로 구현하는 그래프 탐색 알고리즘: DFS와 BFS의 비교

C 언어

그래프 탐색은 컴퓨터 과학에서 필수적인 알고리즘 중 하나로, 다양한 문제를 해결하는 데 사용됩니다. 이 기사에서는 C 언어를 사용하여 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 구현하고, 두 알고리즘의 차이점과 특성을 비교하며, 그래프 표현 방식과 실제 응용 예시를 통해 이해를 심화할 수 있도록 돕습니다.

목차

그래프와 탐색 알고리즘의 기본 개념


그래프는 정점(Node)과 이를 연결하는 간선(Edge)으로 구성된 자료 구조입니다. 그래프는 방향성이 있거나 없을 수 있으며, 가중치를 가질 수도 있습니다.

DFS와 BFS의 탐색 방식

  • 깊이 우선 탐색(DFS): 시작 정점에서 출발하여 한 방향으로 갈 수 있는 만큼 깊이 탐색한 후, 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색합니다.
  • 너비 우선 탐색(BFS): 시작 정점에서 가까운 정점을 먼저 탐색한 후, 점점 더 먼 정점을 탐색해 나가는 방식입니다.

그래프 탐색의 활용


그래프 탐색은 네트워크 연결, 최단 경로 탐색, 퍼즐 문제 해결, 웹 크롤링 등 다양한 분야에서 활용됩니다. DFS와 BFS는 탐색 순서가 다르며, 각 알고리즘은 문제의 성격에 따라 적합한 방식이 다릅니다.

이 두 알고리즘의 기본 원리를 이해하는 것이 그래프 문제를 효과적으로 해결하는 첫걸음입니다.

DFS 구현 및 특징

깊이 우선 탐색(DFS)란?


DFS(Depth-First Search)는 그래프의 시작 정점에서 출발하여 가능한 한 깊이 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아와 다음 경로를 탐색하는 방식입니다. 이 과정은 재귀 호출이나 스택 자료 구조를 통해 구현할 수 있습니다.

DFS의 구현


C 언어에서 DFS를 구현하기 위해 주로 재귀 함수와 인접 리스트를 사용합니다. 아래는 간단한 DFS 코드 예제입니다.

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

#define MAX_NODES 100

// 그래프 표현 (인접 리스트)
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];
int node_count;

// DFS 함수
void dfs(int node) {
    visited[node] = true;
    printf("%d ", node);  // 방문한 노드 출력

    for (int i = 0; i < node_count; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(i);  // 재귀 호출
        }
    }
}

int main() {
    node_count = 5;  // 노드 개수 예시
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[1][4] = graph[4][1] = 1;

    for (int i = 0; i < node_count; i++) {
        visited[i] = false;
    }

    printf("DFS 탐색 순서: ");
    dfs(0);  // 시작 노드
    return 0;
}

DFS의 특징

  1. 시간복잡도: 그래프를 인접 리스트로 표현하면 (O(V + E)), 인접 행렬로 표현하면 (O(V^2)).
  2. 공간복잡도: 재귀 호출로 인해 호출 스택 공간이 필요하며, 방문 배열로 (O(V))의 추가 메모리를 사용.
  3. 응용 분야: 경로 찾기, 사이클 탐지, 위상 정렬, 연결 요소 분리 등.

DFS는 특정 문제에서 빠르게 해답을 찾을 수 있으나, 경로가 깊어질수록 스택 오버플로우 위험이 있다는 점에 유의해야 합니다.

BFS 구현 및 특징

너비 우선 탐색(BFS)란?


BFS(Breadth-First Search)는 시작 정점에서 가까운 정점부터 순차적으로 탐색하며, 탐색 거리가 증가할수록 멀리 있는 정점을 방문하는 방식입니다. 이 과정은 주로 큐 자료 구조를 사용하여 구현됩니다.

BFS의 구현


C 언어에서 BFS를 구현하기 위해 큐를 활용하며, 이는 배열이나 연결 리스트를 통해 쉽게 작성할 수 있습니다. 아래는 BFS의 간단한 구현 예제입니다.

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

#define MAX_NODES 100

int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];
int queue[MAX_NODES];
int front = 0, rear = 0;
int node_count;

// 큐에 요소 추가
void enqueue(int node) {
    queue[rear++] = node;
}

// 큐에서 요소 제거
int dequeue() {
    return queue[front++];
}

// BFS 함수
void bfs(int start_node) {
    enqueue(start_node);
    visited[start_node] = true;

    while (front < rear) {
        int current = dequeue();
        printf("%d ", current);  // 방문한 노드 출력

        for (int i = 0; i < node_count; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = true;
            }
        }
    }
}

int main() {
    node_count = 5;  // 노드 개수 예시
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[1][4] = graph[4][1] = 1;

    for (int i = 0; i < node_count; i++) {
        visited[i] = false;
    }

    printf("BFS 탐색 순서: ");
    bfs(0);  // 시작 노드
    return 0;
}

BFS의 특징

  1. 시간복잡도: 그래프를 인접 리스트로 표현하면 (O(V + E)), 인접 행렬로 표현하면 (O(V^2)).
  2. 공간복잡도: 큐를 사용하므로 (O(V))의 메모리를 추가로 사용.
  3. 응용 분야: 최단 경로 탐색, 네트워크 탐색, 레벨 기반 탐색 등.

BFS는 최단 경로를 찾거나, 같은 레벨의 정점을 그룹으로 처리하는 문제에서 효과적입니다. 다만, 큐 크기가 커질 수 있어 메모리 관리에 주의해야 합니다.

DFS와 BFS의 주요 차이점

탐색 방식의 차이

  • DFS: 한 경로를 끝까지 탐색한 후, 되돌아와 다른 경로를 탐색합니다. 깊이를 우선으로 탐색하기 때문에 그래프의 끝까지 빠르게 도달할 수 있습니다.
  • BFS: 시작 정점에서 가까운 정점부터 탐색하며, 같은 레벨의 정점을 모두 탐색한 뒤 다음 레벨로 넘어갑니다.

시간복잡도와 공간복잡도

  • DFS
  • 시간복잡도: (O(V + E)) (인접 리스트 기준).
  • 공간복잡도: 재귀 호출로 인해 (O(V))의 호출 스택이 필요.
  • BFS
  • 시간복잡도: (O(V + E)) (인접 리스트 기준).
  • 공간복잡도: 큐에 최대 (O(V))의 노드를 저장.

적용 사례의 차이

  • DFS
  • 장점: 깊은 경로를 빠르게 탐색할 수 있어, 경로 탐색 문제(예: 미로 탐색)에 적합.
  • 단점: 깊이가 깊은 그래프에서는 스택 오버플로우 위험.
  • 활용 예시: 위상 정렬, 사이클 탐지, 연결 요소 찾기.
  • BFS
  • 장점: 최단 경로를 보장하며, 레벨 기반 탐색에 적합.
  • 단점: 큐가 커질 수 있어 메모리 사용량이 많아질 수 있음.
  • 활용 예시: 최단 경로 탐색, 네트워크 레벨 탐색, 사회적 네트워크 분석.

예시 비교

  • DFS 탐색 순서: 1 → 2 → 4 → 5 → 3
  • BFS 탐색 순서: 1 → 2 → 3 → 4 → 5

DFS와 BFS는 각기 다른 장단점이 있으므로, 문제의 특성과 요구사항에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

그래프 표현 방식: 인접 리스트와 인접 행렬

그래프 표현의 중요성


그래프를 구현할 때 데이터 구조를 선택하는 것은 알고리즘 성능과 코드 작성의 효율성에 큰 영향을 미칩니다. C 언어에서는 주로 인접 리스트와 인접 행렬 두 가지 방법을 사용하여 그래프를 표현합니다.

인접 리스트

  • 구조: 각 정점이 연결된 정점의 목록을 저장합니다.
  • 구현: 배열과 연결 리스트를 조합하거나, 동적 배열을 사용할 수 있습니다.
  • 장점:
  • 간선 수가 적은 희소 그래프(Sparse Graph)에서 메모리 사용이 효율적.
  • 연결된 정점만 저장하므로 탐색과 간선 추가가 빠름.
  • 단점:
  • 특정 두 정점 간의 연결 여부를 확인하는 데 시간이 더 걸림((O(E))).

예제 코드:

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

Node* graph[MAX_NODES];

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

인접 행렬

  • 구조: (N \times N) 크기의 2차원 배열을 사용하여 정점 간 연결 상태를 나타냅니다.
  • 구현: 배열을 사용하며, (graph[i][j] = 1)이면 (i)와 (j)가 연결됨을 의미합니다.
  • 장점:
  • 두 정점 간의 연결 여부 확인이 (O(1))로 매우 빠름.
  • 정점의 수가 많은 밀집 그래프(Dense Graph)에 적합.
  • 단점:
  • 간선 수가 적을 경우, 메모리 낭비가 발생.
  • 간선 추가나 삭제가 상대적으로 비효율적((O(1))).

예제 코드:

int graph[MAX_NODES][MAX_NODES] = {0};

void addEdge(int src, int dest) {
    graph[src][dest] = 1;
    graph[dest][src] = 1;  // 무향 그래프의 경우
}

인접 리스트와 인접 행렬의 비교

항목인접 리스트인접 행렬
메모리 사용(O(V + E))(O(V^2))
연결 여부 확인(O(E))(O(1))
간선 추가/삭제(O(1))(O(1))
적합한 그래프희소 그래프밀집 그래프

적합한 선택

  • 희소 그래프: 인접 리스트를 사용하여 메모리를 절약하고 효율성을 높임.
  • 밀집 그래프: 인접 행렬을 사용하여 연결 여부 확인을 빠르게 수행.

문제의 성격과 그래프의 특성을 고려해 적합한 표현 방식을 선택해야 합니다.

응용 예시: 미로 탐색

문제 설명


미로 탐색은 시작 지점에서 출발하여 목표 지점에 도달하는 경로를 찾는 문제입니다. 이 문제는 그래프로 모델링할 수 있으며, 각 칸을 정점으로, 인접한 칸 간의 이동을 간선으로 간주합니다.

DFS를 활용한 미로 탐색


DFS는 경로를 깊이 탐색하기 때문에 목표 지점에 도달하는 경로를 빠르게 찾을 수 있습니다.

DFS 코드 예제:

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

#define N 5

int maze[N][N] = {
    {1, 0, 1, 0, 1},
    {1, 1, 1, 1, 1},
    {0, 0, 0, 1, 0},
    {1, 1, 1, 1, 1},
    {1, 0, 1, 0, 1}
};
bool visited[N][N];

int dx[] = {-1, 1, 0, 0};  // 상하좌우 이동
int dy[] = {0, 0, -1, 1};

bool dfs(int x, int y, int dest_x, int dest_y) {
    if (x < 0 || y < 0 || x >= N || y >= N || maze[x][y] == 0 || visited[x][y]) {
        return false;
    }
    if (x == dest_x && y == dest_y) {
        printf("(%d, %d) ", x, y);
        return true;
    }
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (dfs(nx, ny, dest_x, dest_y)) {
            printf("(%d, %d) ", x, y);
            return true;
        }
    }
    return false;
}

int main() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visited[i][j] = false;
        }
    }

    printf("DFS 탐색 경로: ");
    if (!dfs(0, 0, 4, 4)) {
        printf("경로를 찾을 수 없습니다.\n");
    }
    return 0;
}

BFS를 활용한 미로 탐색


BFS는 최단 경로를 보장하므로, 최단 이동 경로를 찾아야 하는 경우 적합합니다.

BFS 코드 예제:

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

#define N 5

int maze[N][N] = {
    {1, 0, 1, 0, 1},
    {1, 1, 1, 1, 1},
    {0, 0, 0, 1, 0},
    {1, 1, 1, 1, 1},
    {1, 0, 1, 0, 1}
};
bool visited[N][N];
int queue[N * N][2], front = 0, rear = 0;

int dx[] = {-1, 1, 0, 0};  // 상하좌우 이동
int dy[] = {0, 0, -1, 1};

bool bfs(int start_x, int start_y, int dest_x, int dest_y) {
    queue[rear][0] = start_x;
    queue[rear++][1] = start_y;
    visited[start_x][start_y] = true;

    while (front < rear) {
        int x = queue[front][0];
        int y = queue[front++][1];

        if (x == dest_x && y == dest_y) {
            printf("도착 지점 (%d, %d)에 도달\n", x, y);
            return true;
        }

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

            if (nx >= 0 && ny >= 0 && nx < N && ny < N && maze[nx][ny] == 1 && !visited[nx][ny]) {
                queue[rear][0] = nx;
                queue[rear++][1] = ny;
                visited[nx][ny] = true;
            }
        }
    }
    return false;
}

int main() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visited[i][j] = false;
        }
    }

    printf("BFS 탐색 경로: ");
    if (!bfs(0, 0, 4, 4)) {
        printf("경로를 찾을 수 없습니다.\n");
    }
    return 0;
}

DFS와 BFS의 비교

  • DFS는 한 경로를 깊이 탐색해 경로를 빠르게 찾을 수 있지만, 최단 경로를 보장하지는 않습니다.
  • BFS는 탐색 시간이 더 걸릴 수 있지만, 항상 최단 경로를 보장합니다.

미로 탐색 문제에서는 요구 사항에 따라 DFS와 BFS 중 적절한 알고리즘을 선택하여 사용합니다.

트러블슈팅: 그래프 탐색 중 흔한 오류와 해결 방법

문제 1: 방문 여부를 제대로 체크하지 않음

  • 현상: 무한 루프 발생 또는 동일 노드를 반복 방문.
  • 원인: 방문 배열(visited[])을 설정하지 않거나 적절히 갱신하지 않은 경우.
  • 해결 방법: 방문 여부를 저장할 배열을 선언하고, 각 노드를 방문할 때마다 갱신합니다.

해결 코드 예시 (DFS):

visited[node] = true;  // 방문 표시
for (int i = 0; i < node_count; i++) {
    if (graph[node][i] == 1 && !visited[i]) {
        dfs(i);
    }
}

문제 2: 재귀 호출로 인한 스택 오버플로우

  • 현상: 깊이 우선 탐색(DFS)에서 호출 스택 크기 초과로 프로그램이 비정상 종료.
  • 원인: 그래프의 깊이가 너무 깊어 재귀 호출 횟수가 많아지는 경우.
  • 해결 방법:
  1. 재귀 대신 명시적 스택을 사용해 DFS를 구현.
  2. 재귀 호출 제한을 설정하거나 그래프를 더 작은 부분으로 나눔.

해결 코드 예시 (스택 기반 DFS):

int stack[MAX_NODES], top = -1;
stack[++top] = start_node;
while (top >= 0) {
    int current = stack[top--];
    if (!visited[current]) {
        visited[current] = true;
        printf("%d ", current);
        for (int i = 0; i < node_count; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                stack[++top] = i;
            }
        }
    }
}

문제 3: 메모리 초과

  • 현상: 그래프가 매우 커서 프로그램 실행 중 메모리 부족이 발생.
  • 원인: 인접 행렬을 사용하여 희소 그래프를 표현하거나, 너무 많은 노드를 저장하려고 하는 경우.
  • 해결 방법:
  1. 인접 리스트로 그래프 표현 방식을 변경.
  2. 필요하지 않은 데이터는 즉시 해제하여 메모리 관리.

문제 4: 큐 사용 중 데이터 손실

  • 현상: BFS에서 방문해야 할 노드가 누락되거나 순서가 틀림.
  • 원인: 큐 구현 오류, 큐가 꽉 찬 경우 데이터가 덮어쓰여짐.
  • 해결 방법: 큐의 크기를 동적으로 관리하거나, 초기화를 철저히 확인.

해결 코드 예시 (동적 큐):

if (rear == MAX_QUEUE_SIZE) {
    printf("큐가 꽉 찼습니다. 크기를 늘립니다.\n");
    rear = 0;  // 필요 시 순환 큐 구현
}
queue[rear++] = node;

문제 5: 그래프 입력 데이터의 형식 오류

  • 현상: 그래프 생성 시 간선이 제대로 추가되지 않음.
  • 원인: 데이터 형식이 문제 정의와 다르거나, 입력 처리가 잘못된 경우.
  • 해결 방법: 입력 데이터를 검증하는 로직을 추가하고, 예외 처리를 통해 오류를 방지.

해결 코드 예시:

if (src < 0 || src >= node_count || dest < 0 || dest >= node_count) {
    printf("잘못된 간선 입력: (%d, %d)\n", src, dest);
    continue;
}
graph[src][dest] = 1;

문제 해결의 중요성


그래프 탐색 알고리즘의 오류는 복잡한 문제를 유발할 수 있습니다. 위의 해결 방법들을 적용해 오류를 예방하고 안정적으로 탐색을 수행하는 것이 중요합니다.

연습 문제: DFS와 BFS 응용

문제 1: 연결 요소 개수 찾기

  • 설명: 무향 그래프에서 연결 요소의 개수를 구하세요. 연결 요소란 모든 노드가 서로 연결된 부분 그래프입니다.
  • 조건: 그래프는 (N)개의 노드와 (M)개의 간선으로 구성됩니다.
  • 입력 예시:
  6 5
  1 2
  2 5
  5 1
  3 4
  4 6
  • 출력 예시:
  연결 요소의 개수: 2

힌트:
DFS나 BFS를 사용하여 방문하지 않은 모든 노드를 탐색하며 연결 요소를 카운트합니다.

문제 2: 미로 최단 경로 찾기

  • 설명: 2차원 배열로 주어진 미로에서 시작점에서 도착점까지의 최단 경로를 찾으세요.
  • 조건:
  • (1)은 이동 가능, (0)은 이동 불가능.
  • (N \times M) 크기의 배열.
  • 입력 예시:
  5 5
  1 0 1 0 1
  1 1 1 1 1
  0 0 0 1 0
  1 1 1 1 1
  1 0 1 0 1

시작점: (0, 0), 도착점: (4, 4).

  • 출력 예시:
  최단 경로 길이: 9

힌트:
BFS를 사용하면 최단 경로를 보장할 수 있습니다. 각 칸의 이동 횟수를 저장하는 배열을 활용합니다.

문제 3: 사이클 탐지

  • 설명: 무향 그래프에서 사이클이 존재하는지 확인하세요.
  • 조건:
  • 입력 그래프는 (N)개의 노드와 (M)개의 간선으로 구성됩니다.
  • 입력 예시:
  3 3
  1 2
  2 3
  3 1
  • 출력 예시:
  사이클 존재: 예

힌트:
DFS를 사용하여 노드를 방문하면서 부모 노드와 자식 노드를 추적하면 사이클을 탐지할 수 있습니다.

문제 4: 최단 경로 거리 출력

  • 설명: 가중치 없는 방향 그래프에서 특정 노드에서 다른 모든 노드까지의 최단 거리를 구하세요.
  • 조건: 그래프는 (N)개의 노드와 (M)개의 간선으로 구성됩니다.
  • 입력 예시:
  5 6
  1 2
  1 3
  3 4
  2 4
  4 5
  3 5

시작 노드: 1.

  • 출력 예시:
  1 -> 2: 1
  1 -> 3: 1
  1 -> 4: 2
  1 -> 5: 2

힌트:
BFS를 활용하여 시작 노드에서 각 노드까지의 거리를 배열에 저장합니다.

연습 문제 풀이 팁

  • 각 문제는 DFS와 BFS를 적절히 활용해 풀 수 있으며, 입력 데이터의 크기에 따라 효율적인 알고리즘을 선택하세요.
  • 문제를 해결한 뒤, 시간복잡도와 공간복잡도를 분석하여 최적화 가능성을 검토해 보세요.

요약


C 언어를 사용한 그래프 탐색 알고리즘 DFS와 BFS의 구현 방법과 특성을 학습했습니다. 두 알고리즘의 차이점, 그래프 표현 방식, 미로 탐색과 같은 응용 예시를 통해 실전 활용 능력을 높였습니다. 또한, 흔한 오류 해결 방법과 연습 문제를 통해 이론적 지식과 실전 문제 해결 능력을 함께 배양했습니다. DFS와 BFS를 적절히 활용해 그래프 문제를 효과적으로 해결할 수 있습니다.

C 언어
BFS C언어 DFS 그래프 탐색 알고리즘
목차