Breadth-First Search (BFS) 개요

BFS는 트리 또는 그래프 구조에서 노드를 너비 우선으로 탐색하는 알고리즘입니다. 시작점에서 출발하여, 현재 레벨의 모든 인접 노드를 먼저 방문한 후 다음 레벨로 이동합니다. 이 방식은 '원형 확장'과 유사하며, 최단 경로 문제에 적합합니다. 왜냐하면 같은 거리의 노드들이 모두 한 번에 처리되기 때문입니다.

주요 특징

• 최단 경로 보장: 같은 간선 가중치(예: 1)가 주어진 경우, 처음 도달한 경로가 항상 최단 경로입니다.
• 큐 기반 구현: 노드 탐색 순서를 보장하기 위해 큐 자료구조를 사용합니다.
• 중복 방문 방지: 각 노드는 한번만 방문되며, 이를 위해 거리 배열이나 해시맵을 이용해 방문 여부를 관리합니다.

문제 해결 예시: 미로 탐색 (AcWing 844)

2차원 격자에서 시작점(0,0)에서 목적지(n-1,m-1)까지의 최단 거리를 구하는 문제입니다. 벽(1)은 통과 불가, 빈 칸(0)은 통과 가능합니다.

핵심 아이디어

• 각 위치의 거리는 전 단계의 거리 + 1로 계산됩니다.
• 방향 이동은 상하좌우 4가지로 고정되어 있으며, 이를 배열로 표현하여 반복문 처리합니다.
• 유효성 검사: 좌표 범위, 벽 여부, 이미 방문 여부를 체크합니다.

코드 구현 (배열 기반 큐)

#include <iostream>
#include <cstring>
#include <algorithm>

const int N = 105;

int n, m;
int grid[N][N];
int dist[N][N];

// 좌표 저장용 배열
std::pair<int, int> queue[N * N];
int head = 0, tail = 0;

// 방향: 위, 오른쪽, 아래, 왼쪽
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int bfs() {
    queue[tail++] = {0, 0};
    memset(dist, -1, sizeof(dist));
    dist[0][0] = 0;

    while (head <= tail) {
        auto [x, y] = queue[head++];
        
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                grid[nx][ny] == 0 && dist[nx][ny] == -1) {
                
                dist[nx][ny] = dist[x][y] + 1;
                queue[tail++] = {nx, ny};
            }
        }
    }
    
    return dist[n-1][m-1];
}

int main() {
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            std::cin >> grid[i][j];
            
    std::cout << bfs() << std::endl;
    return 0;
}

경로 출력을 포함한 확장 버전 (queue + prev 추적)

#include <iostream>
#include <queue>
#include <unordered_map>
#include <cstring>

using namespace std;

const int N = 105;
int n, m;
int grid[N][N];
int dist[N][N];
pair<int, int> prev_node[N][N];
queue<pair<int, int>> q;

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

int bfs() {
    memset(dist, -1, sizeof(dist));
    dist[0][0] = 0;
    q.push({0, 0});

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                grid[nx][ny] == 0 && dist[nx][ny] == -1) {
                
                dist[nx][ny] = dist[x][y] + 1;
                prev_node[nx][ny] = {x, y};
                q.push({nx, ny});
            }
        }
    }

    // 경로 역추적
    int x = n - 1, y = m - 1;
    while (x != 0 || y != 0) {
        cout << x << " " << y << endl;
        auto p = prev_node[x][y];
        x = p.first;
        y = p.second;
    }

    return dist[n-1][m-1];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> grid[i][j];

    cout << bfs() << endl;
    return 0;
}

문제 해결 예시: 8-퍼즐 (AcWing 845)

3×3 격자에서 'x'를 움직여 목표 상태 "12345678x"로 만드는 최소 이동 횟수를 구하는 문제입니다.

핵심 아이디어

• 각 상태는 문자열로 표현 가능 (예: "12345678x").
• 이동은 'x'의 상하좌우로 스왑하는 방식.
• 해시맵 unordered_map<string, int>를 사용해 각 상태의 최단 거리를 저장.
• 큐에 상태 문자열을 넣고, 새로운 상태가 등장하지 않았다면 추가.

코드 구현

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

int bfs(string start) {
    string target = "12345678x";
    queue<string> q;
    unordered_map<string, int> dist;

    q.push(start);
    dist[start] = 0;

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

    while (!q.empty()) {
        string curr = q.front(); q.pop();
        int d = dist[curr];

        if (curr == target) return d;

        int pos = curr.find('x');
        int x = pos / 3, y = pos % 3;

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                int new_pos = nx * 3 + ny;
                swap(curr[pos], curr[new_pos]);

                if (!dist.count(curr)) {
                    dist[curr] = d + 1;
                    q.push(curr);
                }
                swap(curr[pos], curr[new_pos]); // 원상 복귀
            }
        }
    }

    return -1;
}

int main() {
    string state;
    for (int i = 0; i < 9; ++i) {
        char c;
        cin >> c;
        state += c;
    }

    cout << bfs(state) << endl;
    return 0;
}

보너스 팁

• unordered_map<string, int>는 해시 기반으로 평균 O(1) 시간에 삽입/검색이 가능합니다.
• count(key)는 해당 키가 존재하는지 여부를 bool로 반환합니다.
• 방향 벡터 dx[], dy[]를 사용하면 코드의 반복성을 줄이고 유지보수가 쉬워집니다.