[c++] 깊이 우선 탐색 (DFS)

08 Dec 2023

DFS는 특정 경로를 타고 깊이 들어가며 탐색을 수행하는 방식으로 동작합니다. 이 과정에서 방문한 노드를 표시하여 순환을 방지합니다. DFS 알고리즘은 주로 그래프의 연결 여부, 사이클의 존재 여부, 경로의 존재 여부 등을 확인하는 데 활용됩니다.

아래는 C++로 작성된 간단한 DFS 알고리즘의 예시 코드입니다.

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

vector<int> graph[100]; // 그래프의 인접 리스트 표현
bool visited[100]; // 방문 여부를 저장하는 배열

void dfs(int node) {
    visited[node] = true; // 현재 노드를 방문 처리
    cout << node << " "; // 방문한 노드 출력

    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if (!visited[next]) {
            dfs(next); // 방문하지 않은 인접 노드에 대해 재귀적으로 탐색
        }
    }
}

int main() {
    int n, m; // 그래프의 노드 수와 간선 수
    // 그래프 입력 및 초기화 작업 생략
    dfs(0); // 0번 노드부터 DFS 탐색 시작
    return 0;
}

위 코드는 인접 리스트로 표현된 그래프에서 DFS를 수행하는 예시입니다. 이를 통해 DFS가 어떻게 구현되는지 간단히 이해할 수 있습니다.

참고 문헌:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT press.
Skiena, S. S. (2008). The Algorithm Design Manual. Springer Science & Business Media.