[백준 1043번][Kotlin] 거짓말 (분리집합, Union-Find 사용)

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

1043번: 거짓말

 

난이도 : 골드4
태그 : 자료구조, 그래프 이론, 그래프 탐색, 분리 집합

 

 

설명

파티에 진실을 아는 사람이 포함되어 있으면, 그 파티에 참여한 사람들은 모두 진실을 알고 있다고 간주하고,

진실을 알고 있는 사람들이 하나도 포함되어 있지 않는 파티를 카운트하는 문제입니다.

 

문제 태그에도 명시되어 있듯이 그래프 탐색(DFS/BFS)를 통해서도 풀 수 있지만,

분리 집합 (Union - Find 알고리즘 이용)을 통해서도 해결할 수 있습니다.

 

저는 아직 분리집합, Union-Find 알고리즘에 능숙치 않아

분리집합에 익숙해질 겸 분리집합 알고리즘을 사용하여 풀이하였습니다.

 

 

분리집합

분리집합은 서로소 집합이라고도 불립니다.

 

분리, 서로소라는 이름에서 알 수 있듯이,

 

각각의 집합이 공통원소를 가지지 않는 집합입니다.

 

즉, 전체 집합 U에 대해 두개의 집합 A, B가 있을 때,

A ∩ B = Ø 가 성립합니다.

이는 집합이 두개가 아닌 세개 이상일 경우에도 마찬가지로, 각 집합이 공통원소를 가지지 않습니다.

 

본 문제의 경우, 진실을 아는 사람과 모르는 사람, 두 집합으로 나눌 수 있으며,

진실을 아는 경우와 모르는 경우 두개의 상태를 동시에 갖는 사람은 존재하지 않습니다.

 

 

Union - Find 

분리집합은 트리 형태로 나타낼 수 있습니다.

 

각 노드의 부모 번호를 기억하며, 최상위 노드(루트)가 같을 경우 같은 집합으로 봅니다.

 

 

아래는 각 노드의 부모를 넣는 배열입니다.

var parent: Array<Int>

 

fun find(x: Int): Int {
    return if (x == parent[x]) x
    else {
        parent[x] = find(parent[x])
        parent[x]
    }
}

find 알고리즘은 해당 노드의 루트노드를 찾는 함수입니다.

 

노드 x에 대해 자기 자신(x)와 자신의 부모 노드(parent[x])가 같을 경우,

이는 최상위 노드인 루트 노드이며, x를 그대로 리턴하면 됩니다.

 

만약 x와 부모노드가 같지 않다면, 이는 타 노드의 자식노드인 경우로,

parent[x]에 대해 재귀적으로 find를 진행합니다.

 

 

fun union(x: Int, y: Int) {
    val nx = find(x)
    val ny = find(y)

    if (nx != ny) {
        parent[ny] = nx
    }
}

union 메소드는

각 노드 x, y의 부모노드를 찾고,

부모노드가 같지 않을 경우 트리를 병합하는 작업을 수행하는 함수입니다.

 

 

 

소스코드

val br = BufferedReader(InputStreamReader(System.`in`))
val nm = br.readLine().split(" ")
val n = nm[0].toInt() // 사람의 수
val m = nm[1].toInt() // 파티의 수

parent = Array(n + 1) { it }

val knowTruth = Array(n + 1) { false } // 진실을 아는 사람 - true 모르는 사람- false

val stTruth = StringTokenizer(br.readLine(), " ")
repeat(stTruth.nextToken().toInt()) { knowTruth[stTruth.nextToken().toInt()] = true }

 

knowTruth는 진실을 아는 사람을 저장하는 배열입니다.

true일 경우 진실을 아는 사람, false일 경우 모르는 사람입니다.

 

 

val party = Array(m) { ArrayList<Int>() }

repeat(m) { i ->
    val stParty = StringTokenizer(br.readLine(), " ")
    val partyVisitNum = stParty.nextToken().toInt() // 파티에 참여한 사람 수

    for (j in 0 until partyVisitNum) {
        party[i].add(stParty.nextToken().toInt())

        if (j > 0) union(party[i][j], party[i][j - 1])
    }
}

party는 각 파티와 파티에 참여한 사람들을 담는 변수입니다.

 

각 사람들에 대해 union 을 실행하여, 파티에 참여한 사람들의 부모 노드를 같게 만들어줍니다.

 

각 파티에 참여한 사람의 부모는 모두 같은 노드가 되므로,

진실을 아는 사람이 한 명이라도 껴있는 파티는 모두 진실을 아는 집합에 속하게 됩니다.

 

진실을 모르는 사람들끼리만 파티를 할 경우에만, 진실을 아는 사람이 부모 노드가 되지 않습니다.

 

 

val visited = Array(n + 1) { false }
for (i in 1..n) {
    if (knowTruth[i] && !visited[i]) {
        val parent = find(i)

        // 부모가 같은지 비교
        for (j in 1..n) {
            if (parent == find(j)) {
                knowTruth[j] = true
                visited[j] = true
            }
        }
    }
}

 

진실을 아는 사람의 부모노드와 같을 경우, 해당 인물은 진실을 아는 집합에 속하게 됩니다.

 

val knowTruthArrayList = ArrayList<Int>()

for (i in knowTruth.indices) {
    if (knowTruth[i]) knowTruthArrayList.add(i)
}

 

진실을 아는 사람들을 ArrayList에 담습니다.

 

 

var partyCnt = m // 거짓말이 가능한 파티 카운트
repeat(m) { i ->
    for(j in party[i].indices) {
        if(knowTruthArrayList.contains(party[i][j])) {
            partyCnt--
            break
        }
    }
}

println(partyCnt)

partyCnt는 거짓말이 가능한 파티의 갯수를 세는 변수입니다.

전체 파티의 개수(m)으로 초기화하고, 거짓말이 불가능한 파티를 하나씩 만날때마다 1씩 감소합니다.

 

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

lateinit var parent: Array<Int>

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val nm = br.readLine().split(" ")
    val n = nm[0].toInt() // 사람의 수
    val m = nm[1].toInt() // 파티의 수

    parent = Array(n + 1) { it }

    val knowTruth = Array(n + 1) { false } // 진실을 아는 사람 - true 모르는 사람- false

    val stTruth = StringTokenizer(br.readLine(), " ")
    repeat(stTruth.nextToken().toInt()) { knowTruth[stTruth.nextToken().toInt()] = true }

    val party = Array(m) { ArrayList<Int>() }

    repeat(m) { i ->
        val stParty = StringTokenizer(br.readLine(), " ")
        val partyVisitNum = stParty.nextToken().toInt() // 파티에 참여한 사람 수

        for (j in 0 until partyVisitNum) {
            party[i].add(stParty.nextToken().toInt())

            if (j > 0) union(party[i][j], party[i][j - 1])
        }
    }

    val visited = Array(n + 1) { false }
    for (i in 1..n) {
        if (knowTruth[i] && !visited[i]) {
            val parent = find(i)

            // 부모가 같은지 비교
            for (j in 1..n) {
                if (parent == find(j)) {
                    knowTruth[j] = true
                    visited[j] = true
                }
            }
        }
    }

    val knowTruthArrayList = ArrayList<Int>()

    for (i in knowTruth.indices) {
        if (knowTruth[i]) knowTruthArrayList.add(i)
    }

    var partyCnt = m // 거짓말이 가능한 파티 카운트
    repeat(m) { i ->
        for(j in party[i].indices) {
            if(knowTruthArrayList.contains(party[i][j])) {
                partyCnt--
                break
            }
        }
    }

    println(partyCnt)
}


// union - find
fun union(x: Int, y: Int) {
    val nx = find(x)
    val ny = find(y)

    if (nx != ny) {
        parent[ny] = nx
    }
}

fun find(x: Int): Int {
    return if (x == parent[x]) x
    else {
        parent[x] = find(parent[x])
        parent[x]
    }
}

 

 

후기

최소 스패닝 트리 문제를 풀때 처음 union-find 알고리즘을 알게 되었는데,

 

감을 잘 잡지 못하여 union-find에 관련된 다른 문제를 찾아 풀이해보았습니다.

 

분리집합이 뭔지, union-find가 뭔지, 어느정도 감은 잡았는데 자유자재로 응용하기엔 아직 미숙하네요ㅠㅠ

 

좀 더 공부해봐야겠습니다.