[백준] 10451 순열 사이클

Posted on | In

이 문제를 풀면서 굉장히 신기한 경험을 했다. 난 문제가 다 해결이 안 됐는데 맞았습니다! 가 떴다. 너무너무 신기했다. 내가 아직도 모르는 어딘가가 있는 게 분명한데 그걸 뛰어 넘어서 뭔가 틀렸지만 전체적으로 맞는 거 같다는 생각이 든다.

맞았습니다

너무 뜬금 없어서 굉장히 놀랬기도 하고 내가 이만큼 늘었나 싶어서 막 기분이 좋고 그렇다 . ㅎㅎ 어쨌든 내가 100% 이해했다고 생각은 못하기 때문에 오늘은 문제 설명과 얼떨결에 맞춘? 문제에 대한 풀이 설명을 하고 내일 이어서 여기 포스트에다가 수정할 계획이다!

문제 설명

문제 링크 : 10451_순열_사이클

이 문제는 순열 사이클이라는 문제로, 사실 순열이 뭔지 잘 몰라도? 대충 감을 잡아서 풀 수 있다. 이전에는 계속 연결 요소의 개수를 세는 문제를 풀었다면, 이번 문제는 연결 요소 대신 사이클(자기 자신으로 돌아오는)의 수를 세는 문제라고 생각할 수 있다. 여기서 순열을 표현하는 방법이 두 가지가 소개되는데, 첫번째가 배열을 이용해서 표현하는 방법이고 이건 문제에도 설명이 되어 있어서 이해하기가 편하다. 그러나 두 번째 방법이 (3, 2, 7, 8, 1, 4, 5, 6) 이런 식으로 숫자가 랜덤으로 나열되어 있는 방식이고, 선뜻 다가오지 않는다. 그러나 이 말은 곧 1번 노드가 3번 노드로 향하고, 2번 노드는 2번 자신으로, 3번은 7번으로,.. 이런 식으로 i번째 노드가 i번째에 써 있는 노드로 간다는 것을 알아낼 수 있다. 결국 방향그래프에서 사이클이 몇 개인가?를 묻는 문제로 요약할 수 있게 된다.

문제 풀이

1. dfs vs bfs

그럼 어떻게 방향그래프에서 사이클을 감지할 수 있는가? 잠깐 생각해보면 bfs는 넓게 퍼져 나가기 때문에 사이클인지 체크 하기 전에 너무 많은 자식들을 다 데리고 가려고 한다고 생각할 수 있다. 따라서 자식들을 다 데리고 가려는 bfs보다는 하나의 자식에서 그 자식들이 뭐가 있는지 끝장을 보는? dfs가 사이클을 감지하는데 더 알맞다고 생각할 수 있다. 그럼, dfs를 사용해야 한다는 건 어느 정도 감을 잡았는데, dfs를 사용해서 어떻게 사이클을 또 감지할 수 있게 될까?

2. How do we know it is cycle?

감지를 하는데 많은 방법이 있을 수 있겠지만, 나는 그냥 dfs로 다 흝고 돌아왔을 때 나 자신을 또 만나면 사이클이라고 판단하기로 했다. 여기서 나는 tree에서 inorder로 흝을 때 가장 먼저 왼쪽 아래 자식이 흝어진다는 점을 생각했는데, dfs또한 자기의 가장 아래 자식(증증증…증증손주)을 알 수 있다는 점을 알아냈다. 보통 우리가 dfs를 사용하면 void로 정의를 하지만 dfs가 자기의 가장 아래 자식을 return 하도록 한 것이다! 결국 dfs(i)의 return 값이 i와 동일하면 cycle이라는 걸 알아낼 수 있었다.

3. First problem

여기서 나의 문제는 dfs가 visit의 정보를 가지고 있어서 dfs(i)의 return 값이 결국은 i가 되지 못하고 i 바로 전 자식이 된다는 점이었다. 그러니까, if(!visit[x]) 구문 때문에 i가 x 자리에 들어가지 못하고 그 바로 전 값이 return 된다는 거였다. 따라서 나는 i바로 전의 노드(x라고 두자)라면, x의 자식 중에 i가 존재할 것이고 이 경우 x를 return하는 대신 i를 return하도록 했다. 결국 dfs(i)의 return 값이 i바로 전 노드 x가 아니라 x의 자식, 즉 i가 되도록 했다. 그리고, 이런 경우와 함께 아예 i 값이 return되는 경우도 있을 수 있다고 생각했다. 그러나 이 경우는 절대 없었다. 절대 없다 이런 경우는. 따라서 i바로 전 노드를 return할 때 i를 return하도록 코드를 한줄만 더 추가해 주었다.

4. Second problem

또 한가지 문제는, 이렇게만 하면 사이클을 중복해서 흝는다는 점이었다. 만약 내가 (1->2->3->1)의 사이클을 감지해야 하는 경우를 생각한다면 1==dfs(1), 2==dfs(2), 3==dfs(3) 이라 하나의 사이클에서 3번 카운트가 된다는 말이다. 여기서 나는 또 visit를 이용하기로 했다. 만약 사이클로 카운트 되었다면 그 사이클에 들어있는 노드들은 모두 visit[x]=true일 것이므로, visit[x]가 true인 노드들에 대해서는 이게 cycle이던 말던 dfs(x)의 return 값이 x가 아니도록 했다. (0을 return 했다) 만약 사이클이 아닌데 visit[x]가 true인 경우는 어떻하느냐? 생각해 보면 이 경우는 애초에 그 노드를 흝을 때 cycle이 아니라고 판결이 났고 지금은 하나의 노드가 두개의 방향으로 뻩을 수 없기 때문에 고려할 필요가 없다고 생각했다. (얻어 걸린 부분도 조금 있다) 아무튼, visit[x]가 true이면 0을 return하도록 해서 중복을 제외했다.

Unsolved problem

나는 하나의 노드가 두개의 사이클을 가지고 있는 경우 이 방법이 불가능하다고 생각했다. 왜냐하면, 이건 dfs(x)=x일 경우 cnt를 하나 늘리기 때문에 어떤 경로로 사이클이 형성되었는지를 전혀 고려하고 있지 않다. 따라서 하나의 노드가 두개의 사이클을 가질 경우 이 풀이는 사용할 수 없다고 생각해서 백준에 제출할 당시만 해도 틀릴 거라고 생각하고 별 생각이 없었다. 그러나 이 경우를 고려하지 않아도 되는 이유는, 위에서도 언급했지만 하나의 노드는 두 방향으로 뻗을 수 없기 때문이다. 결국, 하나의 노드가 두개의 사이클을 가지는 것은 불가능하다. 따라서 이 경우를 고려하지 않아도 되었다. 나는 어찌저찌 얻어 걸리긴 했지만, 내일 다른 풀이들도 보면서 이 경우를 고려하려면 어떻게 해야 할지도 고민해 볼 예정이다. 그때 더 post를 추가하도록 하겠다!

코드를 첨부한다.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;

int n;
vector<int> adj[1001];
bool v[1001];

int dfs(int x){
    if(v[x]) return 0;
    int ret=x;
    v[x]=true;
    for(int i=0;i<adj[x].size();i++){
        if(!v[adj[x][i]]) {
            ret = dfs(adj[x][i]);
            if(ret==x) {
                //printf("got here!\n");
                return x;
            }
        }
    }
    for(int i=0;i<adj[ret].size();i++){
        if(adj[ret][i]==x) return x;
    }
    return ret;
}

int main(){
    int t, k;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=1;i<=n;i++){
            scanf("%d", &k);
            adj[i].push_back(k);
        }
        
        int cnt=0;
        for(int i=1;i<=n;i++){
            k=dfs(i);
            if(i==k) {
                cnt++;
            }
            //printf("!!!%d %d!!!\n", i, k);
        }
        printf("%d\n", cnt);
        memset(adj, 0, sizeof(adj));
        memset(v, false, sizeof(v));

        // 미해결 부분: 하나의 노드가 두개의 사이클을 가지고 있을 수도 있다. 현재는 모두 하나로 카운트.
        // 난 모르겠지만 맞았습니다! 라고 떴다 완전 신기 나 좀 대박인거같음지금
    }
}