[c++] 경로 탐색 알고리즘

15 Dec 2023

이번에는 C++을 사용하여 경로 탐색 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

깊이 우선 탐색 (DFS)

깊이 우선 탐색은 그래프나 트리를 탐색할 때 많이 사용되는 알고리즘 중 하나입니다. 우선 주어진 시작 노드에서 한 방향으로 탐색을 진행하다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길로 돌아가서 탐색을 다시 진행하는 방식입니다.

다음은 C++으로 깊이 우선 탐색을 구현한 예시입니다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    cout << "Visiting node " << node << endl;

    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if (!visited[next]) {
            dfs(next);
        }
    }
}

int main() {
    int n = 6; // 노드의 수
    graph.resize(n);
    visited.assign(n, false);

    // 그래프 정보 입력
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(5);

    // 시작 노드 지정
    dfs(0);

    return 0;
}

참고 자료

GeeksforGeeks - Depth First Search or DFS for a Graph

이제 경로 탐색 알고리즘을 구현하는 데 도움이 되길 바랍니다.