백준 순열 사이클 Kotlin (dfs, 유니온파인드)

문제 출처 : https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

문제

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

순열을 배열을 이용해 (1…i…nπ1…πi…πn)\(\begin{pmatrix} 1 & \dots & i & \dots &n \\  \pi_1& \dots& \pi_i & \dots & \pi_n \end{pmatrix}\) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

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

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

입력

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

출력

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

알고리즘 분류

• 순열 사이클 분할

풀이

dfs 혹은 bfs 그리고 유니온 파인드로도 풀 수 있는 문제이다.

본인은 dfs, 유니온 파인드 두가지 풀이로 풀었다.

 

dfs

1. 입력 받은 순열의 첫 번째 인덱스부터 dfs를 돌린다.

2. dfs를 돌면 하나의 사이클을 찾을 수 있다.

3. 이미 만들어진 사이클(dfs)에 포함되는 정점은 스킵한다.

4. dfs를 돈 횟수 (사이클의 갯수)를 출력한다.

 

유니온파인드

1. 사이클의 표현을, 각 정점의 부모노드를 숫자가 작은 노드로 몰아서 표현하는 컨셉이다.

2. 두 정점(i,arr[i])를 unionParent로 연결한다.(더 낮은 번호의 노드로 연결)

3. 만약 두 정점이 이미 연결되어있다면 스킵

4. 모든 정점을 연결하고, parent 배열에서 본인을 가리키는 정점의 수를 출력한다.
   (parent 배열에서 본인을 가리키는 정점은 각각 한 사이클의 부모 노드이다.)

 

코드1(dfs)

fun dfs(idx : Int, arr : List<Int> , visited : BooleanArray){
    visited[idx]=true
    val next = arr[idx]-1
    if(visited[next]) return
    dfs(next,arr,visited)
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val t = br.readLine().toInt()
    repeat(t){
        val n = br.readLine().toInt()
        val arr = br.readLine().split(' ').map{it.toInt()}
        var answer=0
        val visited = BooleanArray(n)
        for(i in 0 until n){
            if(visited[i])continue
            dfs(i,arr,visited)
            answer++
        }
        write("$answer\n")
    }
    close()
}

코드2(유니온 파인드)

val br = System.`in`.bufferedReader()

fun getParent(x : Int, parent : IntArray) : Int{
    return if(x==parent[x]) x else getParent(parent[x],parent).also{parent[x]=it}
}

fun unionParent(x : Int, y : Int, parent : IntArray){
    val xx = getParent(x,parent)
    val yy = getParent(y,parent)

    if(xx>yy){
        parent[xx]=yy
    }
    else{
        parent[yy]=xx
    }
}
fun findParent(x : Int, y : Int, parent : IntArray) : Boolean{
    val xx = getParent(x,parent)
    val yy = getParent(y,parent)
    return xx==yy
}

fun main() = with(System.out.bufferedWriter()){

    val t = br.readLine().toInt()
    repeat(t){
        val n = br.readLine().toInt()
        val arr = br.readLine().split(' ').map{it.toInt()}
        val parent = IntArray(n){it}
        var answer=0
        for(i in 0 until n){
            if(!findParent(i,arr[i]-1,parent))
                unionParent(i,arr[i]-1,parent)
        }
        for(i in 0 until n){
            if(parent[i]==i) answer++
        }
        write("$answer\n")
    }
    close()
}