[백준/BOJ] 20040번: 사이클 게임

문제

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

20040번: 사이클 게임

해설

사이클을 구하는 문제이므로 union - find를 이용하여 문제를 풀었다.

union-find는 사이클을 찾는 알고리즘으로 크루스칼 알고리즘을 구현하는데 쓰인다.

https://jjunsu.tistory.com/221

[알고리즘] 크루스칼 알고리즘(Kruscal Algorithm)

이 글에 union - find에 대해 설명이 되있으니 참고하면 될것이다.

반복문을 통해 두 노드에 대해 find() 함수를 수행하여 부모 노드가 같은지 확인을 하고, 

부모 노드가 같다면 사이클이 형성된 것이므로 그 때의 반복횟수가 사이클이 만들어진 횟수가 된다.

코드

import kotlin.collections.ArrayList

private lateinit var parent: IntArray
private lateinit var graph: Array<ArrayList<Int>>

fun main() = with(System.`in`.bufferedReader()) {
    val (pointCnt, orderCnt) = readLine().split(" ").map { it.toInt() }

    parent = IntArray(pointCnt + 1) { i -> i }
    graph = Array(pointCnt) { ArrayList() }

    var cycle = 0
    for(i in 1 .. orderCnt) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        if(find(a) == find(b)) {
            cycle = i
            break
        }

        union(a, b)
    }

    println(cycle)
}

private fun union(a: Int, b: Int) {
    val aRoot = find(a)
    val bRoot = find(b)

    if(aRoot < bRoot) parent[bRoot] = aRoot
    else parent[aRoot] = bRoot
}

private fun find(i: Int): Int {
    if(parent[i] != i) parent[i] = find(parent[i])
    return parent[i]
}