[c++] 너비 우선 탐색을 이용한 검색

15 Dec 2023

알고리즘은 컴퓨터 과학에서 매우 중요한 개념입니다. 너비 우선 탐색(BFS)은 그래프나 트리를 탐색하는 데 사용되는 알고리즘 중 하나입니다. 이번에는 C++을 사용하여 BFS를 이용한 검색 방법에 대해 알아보겠습니다.

너비 우선 탐색(BFS) 알고리즘

너비 우선 탐색은 그래프나 트리를 레벨 단위로 탐색하는 방법입니다. 일반적으로 큐를 사용하여 구현됩니다. 시작 노드부터 인접한 모든 노드들을 방문한 후, 다시 그 노드들의 인접한 노드를 차례로 방문합니다. 각 노드를 방문할 때마다 큐에 추가하여 레벨 단위로 탐색합니다.

C++에서의 너비 우선 탐색(BFS) 구현

아래는 C++에서 너비 우선 탐색을 이용하여 그래프나 트리를 탐색하는 간단한 예제 코드입니다.

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

using namespace std;

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

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

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

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

int main() {
    vector<vector<int>> graph = {{1, 2}, {0, 3, 4}, {0, 5, 6}, {1}, {1}, {2}, {2}};

    bfs(graph, 0);

    return 0;
}

위 코드는 인접 리스트를 사용하여 그래프를 표현하고, 너비 우선 탐색을 수행하는 간단한 예제입니다. 실행 결과로는 시작 노드부터 레벨 단위로 방문한 노드들의 번호가 출력됩니다.

마치며

C++을 이용하여 너비 우선 탐색을 구현하는 방법에 대해 알아보았습니다. 이를 응용하여 다양한 그래프 알고리즘을 구현할 수 있으며, 실제 문제에서도 유용하게 활용됩니다.

더 많은 정보는 C++ Reference에서 확인할 수 있습니다.