[백준] 20040번: 사이클 게임 - Kotlin[코틀린]

문제

 

20040번: 사이클 게임

 

---

풀이

 

 유니온 파인드(Union-Find)를 활용해 풀이하면 된다. 반복문을 통해 입력받은 선분을 합집한(Union) 연산하고 사이클이 발생한 경우에 해당 번호를 출력한다.

 

---

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    var st = StringTokenizer(br.readLine())
    val num = st.nextToken().toInt()
    val case = st.nextToken().toInt()

    val parent = IntArray(num) { it }
    var cnt = 0 // 사이클이 없는 경우 0을 출력한다
    var check = false // 사이클 발생 여부

    fun find(a: Int): Int {
        return if(parent[a]==a) a
        else {
            parent[a] = find(parent[a])
            parent[a]
        }
    }
    fun union(a: Int, b: Int, idx: Int) {
        val x = find(a)
        val y = find(b)
        if(x==y) { // 사이클 발생
            cnt = idx
            check = true
        } else if(x < y) {
            parent[y] = x
        } else {
            parent[x] = y
        }
    }

    repeat(case) {
        st = StringTokenizer(br.readLine())
        if(!check) {
            union(st.nextToken().toInt(), st.nextToken().toInt(), it + 1)
        }
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}