[C++] DFS 관련 문제 (백준 10451번, 순열 사이클)

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

DFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 10451번 "순열 사이클" 문제를 풀이해본다.

---

Reference: https://www.acmicpc.net/problem/10451

문제 분석 및 해결 전략

배열의 두 번째 열 (주어지는 순열)이 다음 노드의 인덱스 (배열의 첫 번째 열)를 결정한다.

그래서 이 문제에서는 어렵지 않게 재귀함수를 생각해볼 수 있다.

DFS의 구조와 유사하게 한 번 방문한 이력이 있는 노드에 다시 이르게 되면 함수 발동이 끝나는 식으로 코드를 작성해볼 수 있다.

그리고 재귀함수가 시작할 때마다 사이클 개수를 하나씩 증가시키면 될 것이다.

구현

#include <iostream>
#include <vector>

using namespace std;

int T, N;
vector<int> graph;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    int next = graph[node];
    if (!visited[next]) {
        dfs(next);
    }
}

int main() {
    cin >> T;

    for (int test = 0; test < T; test++) {
        cin >> N;

        graph.resize(N + 1);
        visited.assign(N + 1, false); // visited를 false로 초기화

        for (int i = 1; i <= N; i++) {
            cin >> graph[i];
        }

        int cycleCount = 0;

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs(i);
                cycleCount++;
            }
        }

        cout << cycleCount << endl;

        // 다음 테스트케이스를 위해 초기화
        graph.clear();
    }

    return 0;
}

코드를 보면 되게 간단한데.. 막상 구현하려고 하면 어떻게 해야할지 바로 그려지지는 않는 것 같다.

DFS 문제에서는 방문 기록을 관리하는 배열 (또는 벡터)가 필요하고, 이것이 재귀함수를 탈출하기 위한 조건으로 사용된다는 것을 확실하게 기억해야겠다.

---

이번 문제는 백준 DFS 문제들 중에서도 정답률이 높은 편에 속한다.

이론 문제나 코딩 문제나 결국 반복하고 많은 문제를 풀어보는 것이 정도인 것 같다.