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

목차

• 너비우선탐색이란?
• 어떤 경우에 사용하는가?
• BFS vs DFS
• 큐 시뮬레이션
• 기본 구현
• floodfill도 BFS인가?
• 결론

 

1. BFS 알고리즘이란?

 

BFS는 그래프에서 가까운 노드부터 차례대로 탐색하는 알고리즘이다.

• 시작 노드를 방문한 후, 그 노드에 인접한 모든 노드를 먼저 방문한다.
• 이후 인접 노드들의 자식 노드들을 다시 차례대로 방문한다.
• 이 과정을 반복하여, 가장 가까운 노드부터 먼 노드까지 넓게 퍼지듯 탐색 -> 너비 우선 탐색
• 시간 복잡도:
  • 그래프가 인접 리스트 형태라면 O(V+E) (V: 정점 수, E: 간선 수)
  • 인접 행렬을 사용한다면, 최악의 경우 O(V^2)
  • 2차원 격자(예: 미로, 그림 채우기)에서의 BFS는 일반적으로 O(N×M)
• 공간 복잡도:
  • 방문 배열(visited), 큐에 의한 메모리 사용을 고려해야 하며, 노드 수가 클수록 공간 요구가 늘어날 수 있다.

 

 인접 리스트 vs 인접 행렬

• 인접 리스트(Adjacency List):
  • 노드마다 연결된 간선들을 리스트로 관리.
  • 정점이 많고, 간선이 비교적 적은 희소 그래프(sparse graph)에 적합.
  • BFS 시, 리스트를 순회하기 때문에 실제 간선 수 E만큼만 탐색.
• 인접 행렬(Adjacency Matrix):
  • 정점 사이 연결 여부를 2차원 배열로 관리(graph[i][j] = 1 or 0).
  • 전체가 조밀한(dense) 그래프에서 간단히 구현 가능.
  • 정점 수가 많으면 O(V^2) 메모리와 연산이 필요.

BFS는 "FIFO" 특성의 Queue 자료구조를 활용한다.

---

2. 어떤 경우에 사용하는가? (활용법)

• 최단 거리를 구하는 경우 (ex. 미로 탈출, 촌수 계산 등)
• 그래프 레벨 탐색 (같은 깊이의 노드들 한 번에 탐색)
• floodfill 알고리즘 (ex. 영역 색칠, 퍼지는 현상 모델링)
• 그래프가 트리 형태가 아니거나, 사이클이 존재하는 경우
• 상태 트리/그래프에서 가장 빠른 해결법 찾기

---

3. BFS vs DFS

항목	BFS	DFS
자료구조	Queue	Stack (또는 재귀)
탐색 방식	가까운 곳부터	깊은 곳부터
사용 목적	최단거리	전체 탐색, 백트래킹
시간/공간	더 많은 메모리 사용 가능성	일반적으로 적음

---

4.  큐 시뮬레이션

0 -> [1, 2]
1 -> [3, 4, 5]
2 -> [6, 7]

큐 시뮬레이션 예시:
[0]         → 방문: 0 → 큐: [1, 2]  
[1, 2]      → 방문: 1 → 큐: [2, 3, 4, 5]  
[2, 3, 4, 5]→ 방문: 2 → 큐: [3, 4, 5, 6, 7]
...

 

핵심 포인트: visited 체크는 큐에 넣을 때 해야 중복 방문을 방지할 수 있다. 

---

5. 기본 구현 (C++ 예시)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void bfs(vector<vector<int>>& graph, int start, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        cout << curr << " ";

        for (int next : graph[curr]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true; // 여기서 체크!
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},      // 0
        {3, 4, 5},   // 1
        {6, 7},      // 2
        {8},         // 3
        {3},         // 4
        {}, {}, {}, {} // 5~8
    };
    vector<bool> visited(9, false);

    bfs(graph, 0, visited); // 출력: 0 1

 

---

 6. floodfill 도 BFS인가?

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

// 예시: BFS로 (x, y)로부터 상하좌우 퍼져 나가기
void floodfill_bfs(int x, int y, vector<vector<int>>& board, vector<vector<bool>>& visited) {
    int n = board.size(), m = board[0].size();
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = true;

    while (!q.empty()) {
        auto [cx, cy] = q.front(); q.pop();
        for (int dir = 0; dir < 4; ++dir) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];

            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (!visited[nx][ny] && board[nx][ny] == 1) {
                    q.push({nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

 

Fllodfill은 2차원 BFS로 생각할 수 있다. 보통 상하좌우(4방향) 탐색을 사용하고, 경우에 따라 8방향 탐색도 사용한다.

---

7. 결론

BFS는 그래프의 넓이(폭)를 우선적으로 탐색하기 때문에, 최단 거리나 퍼짐 현상을 구현할 때 매우 유용하다.

1. 핵심 키워드: Queue, visited 배열, 인접 노드 탐색
2. 구현에서 놓치기 쉬운 부분: 방문 체크 시점은 append할 때
3. 실전에서는 floodfill, 최단 거리, 상태 그래프 탐색에 자주 사용된다