[백준/코틀린] 1043번: 거짓말

링크

1043번: 거짓말

유니온 파인드 (Union-Find)

유니온 파인드란?
두 개의 연산을 통해 서로 겹치지 않는 여러 집합을 관리하는 자료구조입니다.

• Union: 두 원소를 같은 집합으로 합친다.
• Find: 해당 원소가 속한 집합을 찾는다.

경로 압축 (Path Compression)

경로 압축

트리로 집합을 구현하면 트리가 한쪽으로 치우칠 수 있습니다.
경로 압축은 find 연산 중 거쳐간 노드들의 부모를 루트로 바꿔,
이후 find를 더 빠르게 만드는 최적화 방식입니다.
(= “루트를 찾는 김에 부모를 루트로 바꿔버리기”)

parents[v] = find(parents[v])

풀이

유니온 파인드(분리 집합)로 사람들을 묶어 연결 관계를 관리합니다.

진실을 아는 모든 사람을 TRUTH_CLUB과 union하고,
각 파티에 참석한 사람들은 모두 같은 그룹이 되도록 union합니다.

이후 각 파티에 대해,
참석자 중 진실 그룹과 같은 집합에 속한 사람이 한 명이라도 있으면 거짓말을 할 수 없습니다.
진실 그룹과 연결되지 않은 파티의 개수를 세어 출력합니다.

[UnionFind] Union Find의 최적화

코드

lateinit var parents: IntArray
lateinit var parties: List<List<Int>>
const val TRUTH_CLUB = 0

fun union(u: Int, v: Int) {
    val pu = find(u)
    val pv = find(v)

    if (pu != pv) parents[pu] = pv
}

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

    parents[v] = find(parents[v])
    return parents[v]
}

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    parents = IntArray(n + 1) { it }

    readln().split(" ").map { it.toInt() }.drop(1)
        .forEach { union(TRUTH_CLUB, it) }

    parties = List(m) { readln().split(" ").map { it.toInt() }.drop(1) }
        .onEach { party -> party.zipWithNext().forEach { union(it.first, it.second) } }

    println(parties.count { party -> party.none { find(it) == find(TRUTH_CLUB) } })
}