[백준] 17352번. 여러분의 다리가 되어드리겠습니다!(Kotlin)

문제

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

---

풀이(15분)

import java.io.BufferedReader
import java.io.InputStreamReader

private lateinit var parents: MutableList<Int>
private var N = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    N = br.readLine().toInt()

    // 초기화: 0부터 N까지 자기 자신을 부모로
    parents = (0..N).toMutableList()

    repeat(N - 2) {
        val (s, e) = br.readLine().split(" ").map { it.toInt() }
        union(s, e)
    }

    val first = 1
    val second = (2..N).firstOrNull { find(first) != find(it) }

    println("$first $second")
}

fun union(a: Int, b: Int) {
    val rootA = find(a)
    val rootB = find(b)
    if (rootA != rootB) {
        if (rootA > rootB) parents[rootA] = rootB
        else parents[rootB] = rootA
    }
}

fun find(a: Int): Int {
    if (parents[a] == a) return a
    parents[a] = find(parents[a])
    return parents[a]
}

---

문제 풀이 전략

 

사실 가장 대표적이고 간단한 union-find 문제이다.

2024.12.04 - [문제 풀이/도구정리] - [도구정리] Union-Find 알고리즘

[도구정리] Union-Find 알고리즘

 

이를 이해하고 있다면 1번을 기준으로 부모가 다른 단 하나의 도시만을 찾아서 연결해주면 된다는 것을 어렵지않게 이해할 수 있다!