백준 10451번 순열 사이클 :: 마이구미

이번 글은 백준 알고리즘 10451번 "순열 사이클" 을 다뤄본다.

백준 알고리즘 10451번 순열 사이클 문제

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

DFS, BFS 관련 글.

http://mygumi.tistory.com/102

위 그림처럼 사이클 개수를 찾는 문제이다. (방향이 존재함으로 방향 그래프)

정점들이 연결되어 하나의 그래프를 이루는 것을 그래프의 연결 요소라고도 말한다.

즉, 연결 요소의 개수가 순열 사이클의 개수와 같은 의미이므로, 연결 요소를 구하면 되는 문제이다.

이 문제의 이름이 보면, 순열 그래프이다.

순열의 정의 상 숫자는 중복으로 입력되지 않는다고 한다.

그렇다는 건, 그래프가 한개 이상이 존재하지만, 주어지는 그래프는 모든 정점에 연결된 사이클이 있는 그래프라는 것이다.

많은 경우를 생각해야하는 문제처럼 보이지만, 중복 입력이 주어지지 않는다는 것만 파악하면 쉽게 해결할 수 있다.

순열 키워드가 존재하는 이유가 있는 문제이다.

그렇기에, 어렵게 생각할 필요없게 된다.

기본적인 DFS를 활용하면 쉽게 해결할 수 있다.

// 재귀 DFS - 인접리스트
public static void dfs(ArrayList<Integer>[] a, boolean[] c, int v) {

    if (c[v]) {
        return;
    }

    c[v] = true;

    for (int vv : a[v]) {

        if (!c[vv]) {
            dfs(a, c, vv);
        }

    }

}

소스를 보다시피, dfs 호출 시 v를 기준으로 탐색하게 된다.

DFS는 하나의 정점을 기준으로 깊이 탐색하기때문에 한번 DFS를 돌게 된다면, 하나의 연결된 그래프를 탐색한다는 것을 알 수 있다.

각 정점을 기준으로 돌게 되면, 하나의 연결 요소를 탐색하는 것과 같다.

중복된 연결 요소를 탐색하지 않기 위해 각 정점을 기준으로 dfs를 돌릴 경우 조건을 주면 되는 것이다.

for (int i = 1; i <= n; i++) {

    if (!c[i]) {
        dfs(a,c,i);
        components++;
    }

}

전체소스는 Github을 통해 참고하길바란다.

본인 블로그에 그래프 관련 글을 조금 더 있으면 읽어본다면 감사하겠다.

백준 알고리즘 10451번 순열 사이클 문제 전체소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/10451.java