C언어로 너비 우선 탐색(BFS) 구현하기: 코드와 설명

C언어에서 너비 우선 탐색(BFS)는 그래프 또는 트리의 각 노드를 층별로 탐색하는 알고리즘입니다. BFS는 큐(queue)라는 데이터 구조를 사용하여 구현되며, 주로 최단 경로 문제나 연결 요소 탐색 등에서 널리 활용됩니다. 본 기사에서는 BFS의 기본 개념과 원리부터, C언어로 이를 구현하는 방법까지 자세히 다룹니다. 이를 통해 BFS를 활용한 문제 해결 능력을 기를 수 있습니다.

너비 우선 탐색이란?

너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리 구조에서 루트 또는 시작 정점에서 시작하여 인접한 노드들을 먼저 탐색한 뒤, 그 다음 레벨의 노드들을 탐색하는 알고리즘입니다. BFS는 큐(queue)를 이용해 구현되며, 탐색 과정에서 방문한 노드와 방문하지 않은 노드를 명확히 구분합니다.

BFS의 주요 특징

탐색 순서: 깊이보다는 너비를 우선하여 탐색합니다.
최단 경로 보장: 무가중 그래프에서 시작 노드와 목표 노드 간 최단 경로를 찾는 데 유용합니다.
FIFO 방식: 큐를 사용하여 순차적으로 노드를 처리합니다.

BFS의 일반적인 응용

그래프의 연결 요소 찾기
최단 경로 탐색
상태 공간 탐색(예: 퍼즐 문제 해결)

BFS는 효율적이고 직관적인 탐색 알고리즘으로, 다양한 문제에서 널리 활용됩니다.

BFS와 DFS의 차이

너비 우선 탐색(BFS)와 깊이 우선 탐색(DFS)은 그래프 탐색을 위한 대표적인 알고리즘으로, 각각 고유한 방식과 특징을 가지고 있습니다.

탐색 방식의 차이

BFS (Breadth-First Search)
너비를 우선 탐색하며, 동일한 깊이의 모든 노드를 방문한 뒤에 다음 깊이로 진행합니다.
큐(queue)를 사용하여 탐색 순서를 관리합니다.
예시: 시작 정점 A에서 B, C, D를 방문한 후, B의 인접 노드 E, F를 탐색합니다.
DFS (Depth-First Search)
깊이를 우선 탐색하며, 한 경로를 끝까지 탐색한 후에 되돌아옵니다.
스택(stack) 또는 재귀 호출을 사용합니다.
예시: 시작 정점 A에서 B, B의 인접 노드 E를 방문한 후, E의 경로를 모두 탐색한 뒤 다시 A로 되돌아갑니다.

장단점 비교

BFS
장점: 최단 경로 탐색에 적합(무가중 그래프 기준).
단점: 큐를 사용하므로 메모리 사용량이 많아질 수 있음.
DFS
장점: 메모리 사용량이 상대적으로 적음.
단점: 최단 경로를 보장하지 않음.

사용 사례

BFS: 최단 경로 문제, 연결 요소 탐색, 네트워크 거리 계산.
DFS: 사이클 탐지, 경로 존재 여부 탐색, 백트래킹 기반 문제 해결.

두 알고리즘은 문제의 성격과 요구사항에 따라 선택적으로 활용됩니다.

BFS 구현을 위한 준비

C언어에서 너비 우선 탐색(BFS)을 구현하기 위해 알고리즘의 작동 방식을 이해하고, 적절한 데이터 구조를 준비해야 합니다. BFS는 큐(queue)와 방문 여부를 추적할 배열을 활용하여 실행됩니다.

큐(queue)의 역할

큐는 BFS에서 탐색 순서를 관리하기 위해 사용됩니다. BFS는 선입선출(FIFO) 방식으로 노드를 처리하므로, 큐는 다음과 같은 역할을 합니다:

현재 노드의 모든 인접 노드를 저장합니다.
인접 노드 탐색 후, 가장 오래된 노드를 꺼내어 탐색을 진행합니다.

방문 여부 추적

BFS에서는 동일한 노드를 여러 번 방문하지 않도록 방문 여부를 저장하는 배열이 필요합니다.

배열의 크기는 그래프의 노드 수와 동일합니다.
초기값은 모두 0으로 설정하며, 노드 방문 시 1로 변경합니다.

그래프의 표현

BFS를 구현하려면 그래프를 적절한 방식으로 표현해야 합니다. 주로 다음 두 가지 방법이 사용됩니다:

인접 행렬

2차원 배열로 그래프의 모든 연결 상태를 저장합니다.
메모리 사용량이 많지만 구현이 간단합니다.

인접 리스트

연결된 노드만 저장하여 메모리 효율이 높습니다.
동적 메모리 할당을 사용해야 하므로 구현이 다소 복잡합니다.

BFS 구현을 위한 기본 구조

C언어에서 BFS를 구현하려면 다음 구성 요소를 준비합니다:

큐 자료구조
방문 여부 추적 배열
그래프를 저장할 인접 행렬 또는 리스트

이 준비 단계를 마치면 BFS 알고리즘의 코드 구현에 필요한 기반이 갖춰집니다.

C언어에서의 BFS 코드 작성

C언어를 활용하여 너비 우선 탐색(BFS)을 구현하기 위해 큐(queue)와 방문 배열, 그래프 데이터를 설정합니다. 아래는 BFS를 간단히 구현한 예제 코드입니다.

코드 예제

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

#define MAX_NODES 100  // 그래프의 최대 노드 수

int graph[MAX_NODES][MAX_NODES];  // 인접 행렬로 그래프 표현
int visited[MAX_NODES];          // 방문 여부를 저장할 배열
int queue[MAX_NODES];            // 큐 구현을 위한 배열
int front = 0, rear = 0;         // 큐의 앞과 뒤를 나타내는 인덱스

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

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

// 큐가 비어 있는지 확인
int isQueueEmpty() {
    return front == rear;
}

// BFS 함수
void bfs(int startNode, int numNodes) {
    enqueue(startNode);          // 시작 노드를 큐에 추가
    visited[startNode] = 1;      // 시작 노드를 방문 처리

    while (!isQueueEmpty()) {
        int currentNode = dequeue();  // 큐에서 노드 꺼내기
        printf("%d ", currentNode);   // 현재 노드 출력

        // 인접한 노드 탐색
        for (int i = 0; i < numNodes; i++) {
            if (graph[currentNode][i] == 1 && !visited[i]) {
                enqueue(i);          // 인접 노드를 큐에 추가
                visited[i] = 1;      // 방문 처리
            }
        }
    }
}

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

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

    int startNode;
    printf("탐색 시작 노드를 입력하세요: ");
    scanf("%d", &startNode);

    printf("BFS 탐색 순서: ");
    bfs(startNode, numNodes);

    return 0;
}

코드 설명

그래프 표현: 인접 행렬을 사용하여 그래프를 표현합니다.
큐 구현: 배열을 사용하여 큐를 구현하고, 노드 삽입과 삭제를 처리합니다.
BFS 탐색 로직: 시작 노드에서 탐색을 시작하고, 큐를 통해 인접 노드를 순차적으로 방문합니다.
방문 배열: 이미 방문한 노드를 다시 방문하지 않도록 추적합니다.

실행 예시

입력:

노드 수와 간선 수를 입력하세요:  
5 4  
간선을 입력하세요 (시작노드 끝노드):  
0 1  
0 2  
1 3  
2 4  
탐색 시작 노드를 입력하세요:  
0

출력:

BFS 탐색 순서: 0 1 2 3 4

이 코드는 간단한 BFS를 구현하며, 다양한 문제에 쉽게 응용할 수 있습니다.

BFS 알고리즘 실행 흐름

C언어로 작성된 BFS 코드가 실제로 어떻게 동작하는지 단계별로 설명합니다. 이 과정을 이해하면 알고리즘의 작동 원리를 명확히 파악할 수 있습니다.

예제 입력

입력 데이터:

노드 수와 간선 수: 5 4  
간선:  
0 1  
0 2  
1 3  
2 4  
시작 노드: 0

실행 단계

초기화 단계

그래프는 인접 행렬로 저장됩니다.
graph[5][5] = { {0, 1, 1, 0, 0}, {1, 0, 0, 1, 0}, {1, 0, 0, 0, 1}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0} };
방문 배열 visited는 [0, 0, 0, 0, 0]로 초기화됩니다.
큐는 비어 있는 상태에서 시작합니다.

시작 노드 삽입

시작 노드 0을 큐에 추가하고, 방문 배열을 갱신합니다.
queue = [0] visited = [1, 0, 0, 0, 0]

1단계: 노드 0 탐색

큐에서 0을 제거하여 탐색합니다.
0의 인접 노드 1과 2를 큐에 추가합니다.
출력: 0 queue = [1, 2] visited = [1, 1, 1, 0, 0]

2단계: 노드 1 탐색

큐에서 1을 제거하여 탐색합니다.
1의 인접 노드 3을 큐에 추가합니다.
출력: 0 1 queue = [2, 3] visited = [1, 1, 1, 1, 0]

3단계: 노드 2 탐색

큐에서 2를 제거하여 탐색합니다.
2의 인접 노드 4를 큐에 추가합니다.
출력: 0 1 2 queue = [3, 4] visited = [1, 1, 1, 1, 1]

4단계: 노드 3 탐색

큐에서 3을 제거하여 탐색합니다.
3은 더 이상 방문하지 않은 인접 노드가 없습니다.
출력: 0 1 2 3 queue = [4] visited = [1, 1, 1, 1, 1]

5단계: 노드 4 탐색

큐에서 4를 제거하여 탐색합니다.
4는 더 이상 방문하지 않은 인접 노드가 없습니다.
출력: 0 1 2 3 4 queue = [] visited = [1, 1, 1, 1, 1]

탐색 종료

큐가 비어 있으므로 탐색을 종료합니다.

최종 결과

BFS 탐색 순서: 0 1 2 3 4

실행 흐름 요약

노드 탐색은 큐에서 노드를 제거하여 진행됩니다.
인접 노드를 순차적으로 큐에 삽입하고 방문 처리를 수행합니다.
모든 노드가 방문될 때까지 이 과정을 반복합니다.

이 실행 흐름은 BFS의 순차적인 탐색 과정을 이해하는 데 유용합니다.

BFS에서 발생할 수 있는 문제와 해결

너비 우선 탐색(BFS)을 구현하거나 실행할 때 흔히 발생하는 문제와 이를 해결하는 방법을 살펴봅니다. 이러한 문제를 사전에 이해하고 대처하면 효율적이고 오류 없는 BFS 구현이 가능합니다.

문제 1: 무한 루프 발생

원인:

방문 배열을 설정하지 않거나, 노드 방문 처리를 누락한 경우.
이미 방문한 노드를 큐에 반복적으로 삽입.

해결 방법:

방문 여부를 저장하는 배열을 사용하고, 각 노드가 큐에 삽입될 때 방문 처리를 합니다.

  if (!visited[neighbor]) {
      enqueue(neighbor);
      visited[neighbor] = 1;  // 방문 처리
  }

문제 2: 큐 오버플로우

원인:

큐 크기를 그래프의 최대 노드 수보다 작게 설정한 경우.
노드 수가 많은 경우 큐에 너무 많은 노드가 쌓임.

해결 방법:

큐의 크기를 그래프의 최대 노드 수로 설정하거나, 동적 메모리를 사용하여 큐 크기를 확장합니다.

  #define MAX_NODES 1000  // 적절한 큐 크기 설정

문제 3: 그래프 입력 처리 오류

원인:

그래프 데이터 입력 시 형식 오류(예: 간선 데이터 잘못된 형식).
방향 그래프와 무방향 그래프의 처리 혼동.

해결 방법:

입력 형식에 따라 정확히 데이터를 읽고 그래프를 초기화합니다.

  // 무방향 그래프 초기화
  graph[u][v] = 1;
  graph[v][u] = 1;

문제 4: 메모리 초과

원인:

매우 큰 그래프를 인접 행렬로 표현하여 메모리를 과도하게 사용.

해결 방법:

메모리 효율적인 인접 리스트를 사용하여 그래프를 표현합니다.

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

  Node* graph[MAX_NODES];

문제 5: 노드가 분리된 그래프 탐색

원인:

그래프가 분리되어 있을 경우, 한 연결 요소만 탐색하고 나머지를 탐색하지 않음.

해결 방법:

BFS 실행 전에 모든 노드를 순회하여 방문 여부를 확인하고, 방문되지 않은 노드에서 새로운 BFS를 시작합니다.

  for (int i = 0; i < numNodes; i++) {
      if (!visited[i]) {
          bfs(i, numNodes);
      }
  }

문제 6: 성능 문제

원인:

노드와 간선 수가 매우 큰 그래프에서 BFS를 실행할 때, 탐색 속도가 느림.

해결 방법:

그래프의 간선 수를 줄이거나, 문제 요구사항에 맞는 효율적인 탐색 구조로 변경합니다.
특정 조건을 추가하여 탐색 범위를 줄입니다.

트러블슈팅 요약

방문 배열, 적절한 큐 크기, 그래프 입력 형식 등의 기본 요소를 철저히 설정합니다.
복잡한 그래프에서는 메모리와 성능을 고려한 최적화 방안을 적용합니다.

이 문제 해결 전략을 통해 BFS 구현에서 발생할 수 있는 오류를 예방하고, 탐색을 원활히 수행할 수 있습니다.

실전 연습 문제와 확장 응용

너비 우선 탐색(BFS)은 다양한 그래프 문제에 적용될 수 있는 강력한 알고리즘입니다. 이를 활용한 실전 연습 문제와 확장 응용 사례를 통해 BFS의 이해를 심화할 수 있습니다.

연습 문제 1: 그래프의 연결 요소 개수 찾기

문제 설명:
주어진 무방향 그래프에서 연결 요소의 개수를 구하세요. BFS를 사용하여 방문하지 않은 노드에서 탐색을 시작하고, 연결 요소의 개수를 증가시킵니다.

예시 입력:

노드 수: 6  
간선:  
0 1  
1 2  
3 4

예시 출력:

연결 요소 개수: 3

풀이 요약

방문 배열 초기화.
모든 노드를 순회하며 방문하지 않은 노드에서 BFS 수행.
BFS가 종료될 때마다 연결 요소 개수를 증가.

연습 문제 2: 최단 경로 찾기

문제 설명:
BFS를 사용하여 시작 노드에서 특정 목표 노드까지의 최단 경로를 구하세요. BFS는 레벨별 탐색을 수행하므로, 간선의 가중치가 없는 그래프에서 최단 경로를 보장합니다.

예시 입력:

노드 수: 5  
간선:  
0 1  
0 2  
1 3  
2 4  
시작 노드: 0  
목표 노드: 4

예시 출력:

최단 경로: 0 -> 2 -> 4

풀이 요약

BFS 수행 중 목표 노드에 도달하면 탐색을 종료.
부모 노드를 기록하여 최단 경로를 역추적.

응용 사례 1: 퍼즐 문제 해결

BFS는 퍼즐 문제(예: 미로 찾기, 8퍼즐 문제)에서 상태 공간을 탐색하는 데 유용합니다.

예시: 미로에서 출발점에서 도착점까지의 최단 경로를 찾기.
적용: 각 위치를 노드로 간주하고, 이동 가능한 경로를 간선으로 표현하여 BFS 수행.

응용 사례 2: 네트워크 탐색

네트워크 연결 상태나 컴퓨터 바이러스 전파를 분석하는 데 BFS를 활용할 수 있습니다.

예시: 네트워크에서 특정 노드로부터 영향을 받는 노드 집합 찾기.
적용: BFS를 사용해 시작 노드에서 도달할 수 있는 모든 노드를 탐색.

응용 사례 3: 다중 소스 BFS

다중 시작 지점에서 최단 거리를 구하는 문제를 해결할 때, 여러 시작 노드를 큐에 동시에 삽입하여 BFS를 실행합니다.

예시: 불이 번지는 영역에서 안전한 경로 찾기.

실전 연습 문제를 위한 참고 코드

연습 문제를 확장하여 BFS를 사용해 더 복잡한 문제를 해결할 수 있습니다.

// 연결 요소 개수 찾기 예제
int countConnectedComponents(int numNodes) {
    int components = 0;

    for (int i = 0; i < numNodes; i++) {
        if (!visited[i]) {
            bfs(i, numNodes);  // 새로운 연결 요소 탐색
            components++;
        }
    }

    return components;
}

학습과 확장

BFS를 연습 문제에 반복적으로 적용하면 개념이 더욱 명확해집니다.
BFS 알고리즘은 상태 공간 탐색, 네트워크 분석, 퍼즐 해결 등으로 확장 가능성이 높아 실무에서도 자주 활용됩니다.
실전 문제를 풀며 BFS의 효율성과 한계를 경험해보세요.