백준 10451번 [순열 사이클](C++) -yes6686- 티스토리

 

백준 문제 풀이: 10451 [순열 사이클]

---

문제 링크: https://www.acmicpc.net/problem/10451

문제 설명:

1부터 n까지 정수로 이루어진 순열이 주어진다. 이 순열에서 사이클의 개수를 구하는 문제다.

예를 들어 순열이 [2, 1, 4, 3]이라면, 다음과 같이 두 개의 사이클 (1 → 2 → 1), (3 → 4 → 3)로 구성된다.

각 테스트 케이스마다 사이클의 개수를 출력해야 한다.

---

문제 해결 코드

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

int arr[1001];
vector<int> v[1001];
int check[1001];

void dfs(int x) {
    if (check[x]) return;
    check[x] = 1;
    dfs(v[x][0]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
            v[i + 1].push_back(arr[i]);
        }
        for (int i = 1; i <= n; i++) {
            if (!check[i]) {
                ans++;
                dfs(i);
            }
        }
        cout << ans << '\n';
        for (int i = 1; i <= n; i++) {
            v[i].clear();
            check[i] = 0;
        }
    }
}
  

---

코드 설명

• 핵심 알고리즘: DFS를 활용한 사이클 탐색
• 구현 세부사항:
  • v[i]는 i번 정점이 연결된 노드
  • check[i]로 방문 여부 추적
  • DFS를 통해 아직 방문하지 않은 정점에서 시작된 새로운 사이클 개수 탐색
• 시간 복잡도: O(n) per test case – 순열의 각 원소를 한 번씩 방문

---

결과

예시 입력:

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8
  

예시 출력:

3
7
  

각 테스트 케이스마다 DFS로 탐색되는 사이클 개수를 정확히 출력합니다.

이 문제는 순열을 그래프 형태로 해석하고 사이클을 파악하는 능력을 키우기에 매우 좋습니다. 다양한 DFS/BFS 문제 풀이에 연습이 되는 문제입니다.