[백준][Kotlin]1043번 거짓말

해당 문제는 유니온파인드를 이용하여 파티별로 거짓말을 할 수 있는지 확인하여 할 수 있는 만큼 카운터 하여 출력하면 되는 문제입니다.

 

처음에는 거짓말을 할 수 있는 사람들만 있던 파티인데 추후 그 사람들이 진실을 아는 사람들과 파티를 하게 된다면, 지민이는 거짓말 쟁이가 되기 때문에 모든 파티의 참여자들을 확인 한 후 거짓말을 할 수 있는 파티의 수를 카운팅 해야 합니다.

그렇기에 진실을 아는 자들을 한 그룹으로 묶은 뒤에 파티 별 참가자들 중 진실을 아는 자들이 있다면 그 파티에 참가했던 인원들을 모두 만들어 놓은 그룹에 추가하여야 합니다.

 

그리고 다시 파티정보를 조회하여 해당 파티에 진실을 아는자들 그룹에 포함이 되어있는지 확인 한 후 아무도 없다면

카운팅을 증가 시킵니다.

 

마지막으로 만약 진실을 아는 자가 0명 일 경우 모든 파티에서 거짓말을 하더라도 아무도 알 수 없기 때문에

파티의 수 만큼 출력하면 됩니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

 

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

lateinit var human: IntArray
//val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //val bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()+1 // 사람의 수, 배열을 생성하기 위해 처음부터 +1
    val m = st.nextToken().toInt() // 파티의 수

    human = IntArray(n){i: Int ->  i} // 사람의 수
    st = StringTokenizer(br.readLine())
    val truecount = st.nextToken().toInt() // 진실을 아는 사람들의 수
    if(truecount == 0){ // 진실을 아무도 모를 경우
        println(m)
        return
    }
    val firsttrue = st.nextToken().toInt() // 추후 해당 번호를 가지고 있거나 혹은 변경 될 사람이 없는 파티 에서만 거짓말 가능
    for(i in 2 .. truecount){ // 알고 있는 사람들 중 번호가 가장 낮은 사람의 번호로 통일
        human[st.nextToken().toInt()] = firsttrue
    }

    var party = ArrayList<IntArray>() // 파티 별 참가 인원 저장 배열

    for(i in 1 .. m){
        st = StringTokenizer(br.readLine())
        val count = st.nextToken().toInt() // 파티 참석 인원
        var temparr = IntArray(count){_: Int -> st.nextToken().toInt()}
        party.add(temparr)
    }

    for(i in 0 .. party.size-1){ // 파티 별 참가 인원 진실을 아는 사람과 파티가 있는 지 확인
        if(party[i].size == 1) continue
        for(j in 0 .. party[i].size-2){
            union(party[i][j],party[i][j+1])
        }
    }

    var lieCount = 0

    for(i in 0 .. party.size-1){
        if(party[i].size == 1){
            if(find(party[i][0]) != find(firsttrue))lieCount++
            continue
        }
        var check = true
        for(j in 0 .. party[i].size-1){
            if(find(party[i][j]) == find(firsttrue)){
                check = false
                break
            }
        }
        if(check)lieCount++
    }
    println(lieCount)

    //bw.flush()
    //bw.close()
}

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

fun union(a:Int,b:Int){
    val A = find(a)
    val B = find(b)
    if(A != B) {
        if (A < B) human[B] = A
        else human[A] = B
    }
}