[알고리즘] c++ 큐와 BFS

이전 게시물 스택과 재귀와 DFS의 이어서 작성하는 글이다

↓↓

https://hanni01.tistory.com/13

[알고리즘] C++ 스택과 재귀와 DFS

 

---

 

1. 큐

FIFO(First In, First Out) : 먼저 들어온 것이 먼저 나간다.

 

1 → 2 → 3 순서로 들어왔기 때문에 먼저 들어온 1부터 나간다.

파이프처럼 한 쪽으로 들어가고 다른 쪽으로 나가므로 Stack과 달리 들어가는 곳과 나가는 곳의 구분이 있다.

들어오는 곳: Back, push(),  나가는 곳: Front, pop()

 

c++에서의 사용법

#include <queue>
queue<int> q;

q.push(10);       // 10 넣기
q.push(20);       // 20 넣기
q.front();        // 맨 앞 값 (10)
q.back();         // 맨 뒤 값 (20)
q.pop();          // 맨 앞 제거 (10 제거됨)
q.empty();        // 큐가 비었는지?
q.size();         // 현재 큐에 몇 개 들어있는지

 

 

2. BFS(너비 우선 탐색)

BFS는 너비 우선 탐색으로 가까운 노드부터 먼저 탐색하는 방식이다.

그림처럼 레벨 순서대로 탐색이 이루어진다. 각 레벨의 노드를 먼저 모두 탐색하고, 그 다음 레벨로 넘어간다.

1번 노드에서 출발해서, 1번의 자식인 2번과 3번을 동시에 넣고, 2 → 3 순서대로 꺼내서 탐색하며, 그들의 자식인 4, 5, 6, 7을 넣는다.

 

이 과정은 큐를 사용하여 구현된다.

 

BFS에서 큐가 사용되는 이유는

• 위 사진과 같이 1부터 큐에 넣고, 1을 탐색 이후 pop() 그리고, 자식 노드인 { 2, 3 } 을 큐에 넣고 해당 레벨이 끝났으므로 다음레벨로 넘어간다.
• 다음 2번 노드를 탐색하고, pop() 그리고, 2번의 자식 노드인 { 4, 5 }를 큐에 넣고, 같은 레벨인 3번 노드를 탐색한다.

• 3번 노드를 큐에서 꺼내어(pop), 방문한 후 자식 노드인 { 6, 7 }를 큐에 넣고, 해당 레벨이 끝났으므로 다음 레벨로 넘어간다.

설명할 때는 해당 레벨이 끝나면 다음 레벨로 넘어간다라고 적혀있지만, 큐 구조 자체가 자동으로 그 역할을 해주기때문에, 이 부분에 대한 구현은 신경 쓸 필요가 없다.

BFS는 큐에서 노드를 꺼내면서, 해당 노드의 자식 노드들을 큐 뒤에 넣는 방식으로 동작한다.
이렇게 하면 자연스럽게 가까운 노드부터 먼 노드 순서로 탐색이 이루어진다. (레벨 순으로 진행된다.)

---

 

큐로 BFS 구현하기

void bfs(int start, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

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

        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {},           // 0번은 사용 안 함
        {2, 3},       // 1
        {1, 4},       // 2
        {1, 5, 6},    // 3
        {2},          // 4
        {3},          // 5
        {3, 7},       // 6
        {6}           // 7
    };

    cout << "BFS 탐색 순서: ";
    bfs(1, graph);  // 1번 노드에서 시작
    cout << endl;
    return 0;
}

 

---

 

결론!

• BFS는 가까운 노드부터 탐색하는 너비 우선 탐색 방식
• 먼저 들어온 노드부터 탐색하기 위해 FIFO(큐) 구조가 필요
• 큐에 노드를 넣고(push) → 꺼내서 방문(pop)하며 → 자식 노드들을 다시 큐에 넣는 구조