BFS(너비우선 탐색)

그래프 탐색

하나의 노드로부터 모든 노드들을 한 번씩 방문하는 것

BFS(Breadth-First Search)

한 노드에서 옆에 있는 노드(인접한 노드)를 먼저 탐색하는 방법

탐색 과정

레벨(깊이)을 한 단계씩 내려가면서 탐색
1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 넣고 방문처리
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

장단점

장점

1. 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장
2. 최단 경로가 존재하면 깊이가 무한대라도 답을 찾을 수 있음

단점

1. 경로가 길 경우 많은 메모리 공간 필요
2. 해가 존재하지 않으면 모든 그래프 탐색 후 실패로 끝남
3. 노드의 수가 늘어나면 탐색해야하는 노드가 많아져 비효율적

구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> queue;
    vector<int> visitedOrder; // 방문한 노드를 저장하는 배열
    
    queue.push(start);
    visited[start] = true;
    
    while (!queue.empty()) {
        int node = queue.front();
        queue.pop();
        visitedOrder.push_back(node); // 방문한 노드를 저장
        
        // graph[node]에 연결된 모든 노드를 순회
        for (int adj : graph[node]) {
            if (!visited[adj]) {
                visited[adj] = true;
                queue.push(adj);
            }
        }
    }
    
    // 방문한 노드 출력
    cout << "방문한 노드 순서: ";
    for (int node : visitedOrder) {
        cout << node << " ";
    }
    cout << endl;
}

int main() {
    // 예시 그래프
    vector<vector<int>> graph = {
        {1, 2}, // 0과 연결된 노드
        {3, 4}, // 1과 연결된 노드
        {5, 6}, // 2와 연결된 노드
        {7},    // 3과 연결된 노드
        {},     // 4와 연결된 노드
        {},     // 5와 연결된 노드
        {8, 9}, // 6과 연결된 노드
        {},     // 7과 연결된 노드
        {10},   // 8과 연결된 노드
        {},     // 9와 연결된 노드
        {}      // 10과 연결된 노드
    };
    
    bfs(graph, 0); // 0번 노드부터 BFS 시작
    return 0;
}

관련 문제

문제1

참고자료

자료1
탐색과정
장단점