[c++] 그래프 기반 검색 알고리즘

15 Dec 2023

그래프는 노드와 노드 사이의 연결관계를 나타내는 자료구조로, 많은 실제 상황을 표현할 수 있습니다. 따라서 그래프를 다루는 검색 알고리즘은 매우 중요합니다. 여기서는 대표적인 그래프 기반 검색 알고리즘에 대해 살펴보겠습니다.

깊이 우선 탐색 (DFS, Depth-First Search)

깊이 우선 탐색(DFS)은 그래프 구조를 탐색할 때 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 이 알고리즘은 스택(Stack) 자료구조를 활용하여 구현됩니다. 깊이 우선 탐색은 미로 찾기와 같은 경로 문제에 적합합니다.

DFS 예제 코드

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

vector<vector<int>> graph; // 그래프
vector<bool> visited;      // 방문 여부를 저장하는 배열

void dfs(int node) {
    visited[node] = true; // 노드 방문 처리
    cout << node << " ";  // 방문한 노드 출력
    
    for (int next : graph[node]) {
        if (!visited[next])  // 방문하지 않은 노드일 경우
            dfs(next);       // 해당 노드로 이동
    }
}

int main() {
    int n;  // 노드 개수
    int m;  // 간선 개수
    cin >> n >> m;

    graph.resize(n + 1);
    visited.resize(n + 1, false);

    for (int i = 0; i < m; ++i) {
        int u, v;  // 간선 정보
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);  // 무방향 그래프일 경우
    }

    dfs(1);
    return 0;
}

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

너비 우선 탐색(BFS)은 그래프 구조를 탐색할 때 인접한 모든 노드를 우선적으로 탐색하는 알고리즘입니다. 이 알고리즘은 큐(Queue) 자료구조를 활용하여 구현됩니다. 너비 우선 탐색은 최단 경로 문제나 가까운 노드 우선 순위 문제에 적합합니다.

BFS 예제 코드

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

vector<vector<int>> graph; // 그래프
vector<bool> visited;      // 방문 여부를 저장하는 배열

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;  // 시작 노드 방문 처리

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";  // 방문한 노드 출력
        
        for (int next : graph[node]) {
            if (!visited[next]) { // 방문하지 않은 노드일 경우
                q.push(next);
                visited[next] = true;  // 해당 노드 방문 처리
            }
        }
    }
}

int main() {
    int n;  // 노드 개수
    int m;  // 간선 개수
    cin >> n >> m;

    graph.resize(n + 1);
    visited.resize(n + 1, false);

    for (int i = 0; i < m; ++i) {
        int u, v;  // 간선 정보
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);  // 무방향 그래프일 경우
    }

    bfs(1);
    return 0;
}

결론

그래프 기반의 탐색 알고리즘은 실생활에서 다양한 문제에 적용할 수 있으며, DFS와 BFS는 그 중에서도 대표적인 알고리즘입니다. 이러한 알고리즘을 제대로 이해하고 활용함으로써 많은 문제들을 해결할 수 있습니다.

깊이 우선 탐색 (DFS)
너비 우선 탐색 (BFS)