탐색 - 8. 너비 우선 탐색(BFS, Breadth First Search)

📌 8. 너비 우선 탐색(BFS, Breadth First Search)

---

8.1 BFS 개념 및 원리

🔹 BFS(Breadth First Search)란?

BFS(너비 우선 탐색)는 그래프에서 가까운 정점부터 탐색을 진행하는 방식입니다.
한 정점에서 출발하여 모든 인접한 정점을 먼저 방문한 후, 다음 깊이로 이동하는 방식입니다.

💡 BFS의 특징

• 모든 정점을 한 단계씩 탐색 → 가까운 노드부터 방문
• 최단 경로(Shortest Path) 탐색에 유리 → 최단 거리 문제 해결 가능
• 트리/그래프 탐색, 네트워크 연결 확인, AI 경로 탐색 등에 활용

---

🔹 BFS 탐색 원리

1. 시작 정점을 큐(Queue)에 삽입하고 방문 처리
2. 큐에서 정점을 꺼내어 인접한 정점들을 방문
3. 모든 정점을 방문할 때까지 반복

✔ 예제 그래프

  1 - 2
  |   |
  3 - 4 - 5

BFS 탐색 순서: 1 → 2 → 3 → 4 → 5
✔ 깊이 우선 탐색(DFS)와 달리, 같은 깊이의 정점들을 먼저 방문!

---

8.2 BFS의 시간 복잡도 분석

🔹 BFS의 시간 복잡도: O(V + E)

• 각 정점(Vertex)은 한 번씩 방문되므로 O(V)
• 각 간선(Edge)도 한 번씩 검사되므로 O(E)
• 따라서, 총 시간 복잡도는 O(V + E)

🔹 인접 행렬(Adjacency Matrix) vs 인접 리스트(Adjacency List)에서의 시간 복잡도

그래프 표현 방식	탐색 시간 복잡도
인접 행렬 (Adjacency Matrix)	O(V²)
인접 리스트 (Adjacency List)	O(V + E)

💡 일반적으로 인접 리스트가 더 효율적이므로, 그래프 탐색에서는 인접 리스트를 선호합니다.

---

8.3 큐(Queue) 자료구조를 이용한 BFS 구현 방식

BFS는 큐(Queue) 자료구조를 이용하여 구현됩니다.

자료구조	설명
큐(Queue)	FIFO(First In First Out, 먼저 들어간 데이터가 먼저 나옴) 방식
BFS 탐색 방식	1) 큐에 삽입, 2) 정점 탐색, 3) 인접 정점 큐 삽입, 4) 반복

✔ 큐는 배열(Array) 또는 연결 리스트(Linked List)로 구현 가능

---

8.4 BFS의 활용 예시

🔹 1) 최단 경로 문제 해결 (Shortest Path)

• BFS는 가중치가 없는 그래프에서 최단 경로 탐색에 유리함
• 예: 미로 탈출 문제, 네트워크 연결 탐색, 전염병 확산 분석

🔹 2) 네트워크 연결 확인

• BFS를 이용하여 모든 노드가 연결되었는지 확인 가능
• 예: 컴퓨터 네트워크, SNS 친구 추천 시스템

---

🔍 실습: 큐를 이용한 BFS 구현

1️⃣ 기본 BFS 구현 (C 언어)

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

#define V 5  // 정점 개수

// 그래프 인접 행렬
int graph[V][V] = {
    {0, 1, 1, 0, 0},
    {1, 0, 0, 1, 0},
    {1, 0, 0, 1, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 1, 1, 0}
};

// BFS 탐색 함수
void BFS(int start) {
    int visited[V] = {0}; // 방문 여부 저장
    int queue[V]; // 큐 배열
    int front = 0, rear = 0; // 큐 포인터

    queue[rear++] = start; // 시작 정점을 큐에 삽입
    visited[start] = 1;

    printf("BFS 탐색 순서: ");

    while (front < rear) {
        int node = queue[front++]; // 큐에서 정점 꺼내기
        printf("%d ", node);

        // 인접 정점을 큐에 추가
        for (int i = 0; i < V; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
    printf("\n");
}

int main() {
    BFS(0); // 0번 정점부터 BFS 탐색 시작
    return 0;
}

📌 실행 결과

BFS 탐색 순서: 0 1 2 3 4

✔ 큐를 이용해 가장 가까운 정점부터 탐색!

---

2️⃣ 최단 경로 문제 해결 (미로 탈출)

BFS는 최단 경로를 찾는 데 유용하므로, 미로 탈출 문제를 해결하는 예제입니다.

✔ 미로 설명 (0: 이동 가능, 1: 벽)

S 1 0 0 0
0 1 0 1 0
0 0 0 1 E
1 1 1 1 0
0 0 0 0 0

✔ 출발점(S) → 출구(E)까지의 최단 경로 찾기

#include <stdio.h>

#define N 5

// 미로 지도 (0: 이동 가능, 1: 벽)
int maze[N][N] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

// 방향 벡터 (상, 하, 좌, 우)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// BFS 탐색 함수
int BFS_maze(int startX, int startY) {
    int queue[N * N][2], front = 0, rear = 0; // 큐 초기화
    int visited[N][N] = {0}; // 방문 여부 저장

    queue[rear][0] = startX;
    queue[rear][1] = startY;
    rear++;
    visited[startX][startY] = 1;

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

        // 출구 도착
        if (x == N - 1 && y == N - 1) {
            return 1; // 출구 도착
        }

        // 네 방향 이동
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

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

    return 0; // 출구에 도달할 수 없음
}

int main() {
    if (BFS_maze(0, 0)) {
        printf("미로 탈출 성공!\n");
    } else {
        printf("출구에 도달할 수 없습니다.\n");
    }
    return 0;
}

📌 실행 결과

미로 탈출 성공!

✔ BFS를 사용하여 출구까지의 최단 경로를 성공적으로 탐색!

---

📌 마무리 및 정리

• BFS는 너비 우선 탐색 방식으로 가까운 정점부터 탐색
• 큐(Queue) 자료구조를 사용하여 구현
• 최단 경로 문제에 유리하며, 미로 찾기, 네트워크 연결 확인 등에 활용
• 시간 복잡도 O(V + E)
  • V(정점 개수), E(간선 개수)에 따라 성능이 결정됨
  • 인접 리스트를 활용하는 것이 인접 행렬보다 더 효율적

---

📌 BFS vs DFS 비교

비교 항목	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 방식	가까운 노드부터 탐색	깊이 우선 탐색
사용 자료구조	큐(Queue)	스택(Stack) 또는 재귀(Recursive)
최단 경로 탐색	✅ 적합 (최단 거리 보장)	❌ 보장되지 않음
공간 복잡도	O(V) (큐 사용)	O(V) (스택 또는 재귀 호출)
적용 사례	미로 탐색, 최단 경로 문제, 네트워크 분석	미로 찾기, 위상 정렬, 백트래킹 문제

💡 BFS는 최단 경로 탐색에 적합, DFS는 깊이 탐색이 필요한 경우 유용!