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

15 Dec 2023

깊이 우선 탐색 (DFS)은 그래프나 트리와 같은 자료 구조를 탐색하기 위한 알고리즘 중 하나입니다. DFS는 한 정점으로부터 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색합니다.

DFS 알고리즘 개요

DFS 알고리즘은 다음과 같은 과정을 거칩니다:

첫 번째 정점을 방문한다.
첫 번째 정점과 연결된 정점들을 방문한다.
연결된 정점 중에서 방문하지 않은 정점이 있으면 그 정점을 시작 정점으로 하여 다시 1번부터 과정을 반복한다.
모든 정점을 방문할 때까지 반복한다.

DFS 코드 예시

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph; // 인접 리스트 형태의 그래프
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    cout << "방문한 노드: " << node << endl;

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

int main() {
    int n, 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); // 1번 노드부터 시작

    return 0;
}

위의 코드는 DFS를 이용하여 그래프를 탐색하는 간단한 예시입니다.

마무리

DFS는 그래프의 모든 노드를 방문하기 위해 사용되며, 깊이 우선 탐색을 통해 그래프의 구조를 파악할 수 있습니다. 그러나 DFS의 시간 복잡도는 정점과 간선의 개수에 선형적으로 의존하므로, 큰 규모의 그래프에서는 성능에 주의해야 합니다.

참고 문헌: GeeksforGeeks