백준 [1043] kotlin

[문제]

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

1043번: 거짓말

[풀이]

가장 핵심은 진실을 아는 사람에게는 진실을 말해야 한다는 것이다.

이를 통해 추가적으로 알 수 있는 것은 진실을 아는 사람이 있는 파티에 있는 사람들도 진실을 알아야 한다는 것이다.

 

파티 배열을 순환하면서, 진실을 아는 사람이 있는 배열을 파티 배열에서 제거를 하고, 진실을 알고 있는 사람들이 담긴 배열에 추가를 한다.

파티 배열을 반복할 때 파티 배열이 더 이상 줄지 않으면, 더 이상 진실을 알아도 되는 사람이 있는 파티는 없으므로, 

구한 파티는 결국 과장을 해도 되는 파티가 된다.

 

<과정>

파티의 수가 줄지 않을 때까지 아래의 과정을 반복한다.

진실을 알아야 하는 사람들의 배열의 집합과 파티의 교집합을 했을때 공집합이 아니라면, 파티 목록에서 제거를 하고 진실을 알아햐 하는 사람들 목록에 추가를 한다.

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

lateinit var truth : MutableSet<Int>
lateinit var party : ArrayList<ArrayList<Int>>
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    var tmp = br.readLine().split(" ").map{it.toInt()}
    var M = tmp[1]

    truth = mutableSetOf()
    party = arrayListOf()
    tmp = br.readLine().split(" ").map{it.toInt()}
    repeat(tmp[0])
    {
        i ->
        truth.add(tmp[i+1])
    }
    repeat(M)
    {
        i ->
        tmp = br.readLine().split(" ").map{it.toInt()}
        tmp = tmp.drop(1)
        party.add(ArrayList(tmp))
    }
    while(true)
    {
        val start = party.size
        val tmp = arrayListOf<ArrayList<Int>>()
        for(i in party)
        {
            if(i.intersect(truth).isNotEmpty()) tmp.add(i)
        }
        for(i in tmp) {
            party.remove(i)
            truth.addAll(i)
        }
        if(start == party.size) break
    }
    bw.write(party.size.toString())
    bw.flush()
    bw.close()
}