[백준/C++] 10451 번 : 순열 사이클 풀이

10451번 : 순열 사이클

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

10451번: 순열 사이클

---

문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 (1234567832781456) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 (1…i…nπ1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

 

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

---

간단한 방향 그래프 DFS 문제이다.

 

참고하면 좋은 비슷한 문제 1 : 백준 2616 바이러스 

silver-g-0114.tistory.com/99

[백준/C++] 2606 번 : 바이러스 풀이

참고하면 좋은 비슷한 문제 2 : 백준 11724 연결 요소의 개수

silver-g-0114.tistory.com/20

[백준/C++] 11724번 : 연결 요소의 개수 풀이

위의 두 문제는 무방향 그래프 DFS 문제이므로, 방향 그래프 DFS 로 적절히 바꿔 풀면 된다.

 

전체 코드

#include <iostream>
#include <cstring>
#define MAX 1001

using namespace std;

int t, n, ans, arr[MAX];
bool visited[MAX];

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

int main(void){
    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> t;
    
    while(t--){
        memset(visited, false, sizeof(visited));
        memset(arr, 0, sizeof(arr));
        ans = 0;
        
        cin >> n;
        for(int i=1; i<=n; i++){
            cin >> arr[i];
        }
        
        for(int i=1; i<=n; i++){
            if(!visited[i]){
                ans++;
                dfs(i);
            }
        }
        cout << ans << '\n';
    }
    
    return 0;
}

 

풀이 인증