C언어로 BFS 구현하기

BFS(Breadth-First Search)는 그래프나 트리를 탐색하는 알고리즘 중 하나로, 시작 정점에서 가까운 정점부터 탐색하는 방식입니다. BFS는 큐(Queue)를 사용하여 구현되며, 각 정점을 방문할 때마다 그 정점과 연결된 모든 인접 정점을 큐에 추가합니다.

BFS의 동작 방식

1. 시작 정점을 방문하고 큐에 추가합니다.
2. 큐에서 정점을 꺼내 그 정점과 연결된 모든 인접 정점 중 아직 방문하지 않은 정점을 방문합니다.
3. 방문한 정점들을 큐에 추가합니다.
4. 큐가 비어 있을 때까지 2번과 3번을 반복합니다.

C언어로 BFS 구현하기

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

#define MAX 100

// 그래프를 표현하기 위한 인접 리스트 구조체
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX]; // 인접 리스트
int visited[MAX];   // 방문 여부를 기록하는 배열

// 새로운 노드 생성 함수
Node* createNode(int vertex) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

// 그래프에 간선 추가 함수
void addEdge(int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;

    // 무방향 그래프인 경우 반대 방향 간선도 추가
    newNode = createNode(src);
    newNode->next = adjList[dest];
    adjList[dest] = newNode;
}

// BFS 함수
void BFS(int startVertex) {
    int queue[MAX], front = 0, rear = 0;
    visited[startVertex] = 1; // 시작 정점 방문 표시
    printf("%d ", startVertex); // 방문한 정점 출력
    queue[rear++] = startVertex; // 큐에 시작 정점 추가

    while (front < rear) {
        int currentVertex = queue[front++]; // 큐에서 정점 꺼내기
        Node* temp = adjList[currentVertex];

        while (temp) {
            int connectedVertex = temp->vertex;
            if (!visited[connectedVertex]) {
                visited[connectedVertex] = 1; // 방문 표시
                printf("%d ", connectedVertex); // 방문한 정점 출력
                queue[rear++] = connectedVertex; // 큐에 추가
            }
            temp = temp->next;
        }
    }
}

int main() {
    // 그래프 초기화
    for (int i = 0; i < MAX; i++) {
        adjList[i] = NULL;
        visited[i] = 0;
    }

    // 간선 추가 (예: 0-1, 0-2, 1-3, 1-4, 2-5)
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 5);

    printf("BFS 결과: ");
    BFS(0); // BFS 시작 정점

    return 0;
}

1. 그래프 표현: 인접 리스트를 사용하여 그래프를 표현합니다.
2. 간선 추가: addEdge 함수를 통해 간선을 추가합니다. 무방향 그래프를 고려하여 양 방향으로 간선을 추가합니다.
3. BFS 구현: BFS 함수는 큐를 사용하여 정점을 방문하고 인접 정점을 큐에 추가합니다.
4. 메인 함수: 그래프를 초기화하고 간선을 추가한 후, BFS를 시작합니다.

사용 예시

1. 최단 경로 탐색: 가중치가 없는 그래프에서 두 정점 간의 최단 경로를 찾는 데 효과적입니다. BFS는 각 단계에서 가장 가까운 정점을 먼저 탐색하기 때문에 최단 경로를 보장합니다.
2. 레벨 탐색: 그래프의 레벨 구조를 탐색할 때 유용합니다. 예를 들어, 특정 깊이의 노드를 찾거나, 트리의 모든 노드를 레벨별로 탐색할 때 사용됩니다.
3. 연결 요소 탐색: 그래프의 연결 요소를 찾는 데에도 BFS가 사용됩니다. 각 연결 요소를 별도로 탐색하여 그래프의 구조를 이해할 수 있습니다.
4. 미로 찾기: 미로와 같은 문제에서 출구까지의 최단 경로를 찾는 데 유용합니다.
5. 네트워크 흐름 문제: 네트워크 흐름 알고리즘에서 경로를 찾는 데 BFS를 사용할 수 있습니다.

---

BFS를 이용해 이미지 프로세싱 프로그램을 구현할 수 있습니다.

Softeer - 현대자동차그룹 SW인재확보플랫폼

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

#define MAX_H 128
#define MAX_W 128
#define QUEUE_SIZE (MAX_H * MAX_W)

typedef struct {
    int x;
    int y;
} Point;

int H, W;
int image[MAX_H][MAX_W];
bool visited[MAX_H][MAX_W];

void bfs(int start_x, int start_y, int target_color, int new_color) {
    Point queue[QUEUE_SIZE];
    int front = 0, rear = 0;

    queue[rear++] = (Point){start_x, start_y};
    visited[start_x][start_y] = true;
    image[start_x][start_y] = new_color;

    while (front < rear) {
        Point current = queue[front++];
        
        int dx[] = {1, -1, 0, 0}; // 아래, 위, 오른쪽, 왼쪽
        int dy[] = {0, 0, 1, -1};

        for (int i = 0; i < 4; i++) {
            int new_x = current.x + dx[i];
            int new_y = current.y + dy[i];

            if (new_x >= 0 && new_x < H && new_y >= 0 && new_y < W &&
                !visited[new_x][new_y] && image[new_x][new_y] == target_color) {
                
                visited[new_x][new_y] = true;
                image[new_x][new_y] = new_color;
                queue[rear++] = (Point){new_x, new_y};
            }
        }
    }
}

int main() {
    scanf("%d %d", &H, &W);

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            scanf("%d", &image[i][j]);
        }
    }

    int Q;
    scanf("%d", &Q);

    for (int q = 0; q < Q; q++) {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        x--;
        y--;

        int target_color = image[x][y];
        if (target_color != c) {
            // 각 연산의 visited 초기화
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    visited[i][j] = false;
                }
            }
            bfs(x, y, target_color, c);
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            printf("%d", image[i][j]);
            if (j < W - 1) printf(" ");
        }
        printf("\n");
    }

    return 0;
}