[백준] 10451 순열 사이클 (1)

Posted on | In

어제 내가 이 문제를 풀고 풀이를 본다고 그랬는데 진짜로 다른 사람들 풀이를 확인해 보니까 더욱 더 간단했다. 문제 자체가 굉장히 쉬운? 축의 문제라 걸어줘야 하는 조건들이 많이 없어서 어제도 잘 됐고 다른 사람들 풀이도 간단한 것 같다.

참고한 풀이

내가 참고한 풀이의 링크는 다음과 같다. 링크 다른 분들도 비슷하게 푼 것 같다.

간단히 풀이를 설명해 보자면, 그냥 dfs를 돌면서 연결 요소 때랑 똑같이 count 해주면 된다. 그럼 왜 사이클을 세는 거랑 연결 요소를 세는 거랑 똑같은가? 이 문제가 굉장히 간단해지는 이유이다. 이 문제(순열 사이클)에 있는 노드들은 무조건 하나의 사이클에 포함이 되어 있다! 결국 탐색을 할 때 걔가 사이클이 아닐 확률이 0이라는 거다. 그래서 이게 사이클인지를 따져줄 필요가 없고, 그냥 dfs 탐색을 돌면서 새로운 dfs 탐색이 시작되면(새로운 사이클이 시작되면) count를 늘려 주기만 하면 되는 거다. 너무 간단해서 눈물 날 뻔 했지만 어쨌든 굉장히 간단하고 결국 또 연결 요소의 개수 문제와 동일해졌다. 그래서 사실 bfs를 써도 문제가 풀릴 거 같은? (왜냐면 노드 하나는 무조건 단 하나의 자식을 가진다) 느낌이다.

코드를 첨부한다. 이건 풀이 방법만 보고 코드는 내가 짠 거다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <vector>
using namespace std;

int n; 
bool v[1001];
int adj[1001]; // adj[a]=b : a의 자식이 b다

void dfs(int x){
    if(v[x]) return; // 사이클 만나면 어쨌든 멈추기는 해야 한다
    v[x]=true;
    if(adj[x]) dfs(adj[x]);
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=1;i<=n;i++) scanf("%d", &adj[i]);

        int cnt=0;
        for(int i=1;i<=n;i++){
            if(!v[i]) {
                dfs(i);
                cnt++;
            }
        }
        for(int i=1;i<=n;i++) {
            v[i]=false;
            adj[i]=0;
        }

        printf("%d\n", cnt);
    }
}