백준 1043 코틀린

완전 탐색과 유니온 파인드 두가지 이상의 방식으로 풀이 가능한 문제이다.
제일 먼저 떠오른게 완전 탐색인데 dfs로 풀려면 각 참석자가 참가한 파티나 같이 파티를 참석한 사람들의 정보가 필요하여
그냥 while문과 set contains(big O (1))를 이용하여 완전 탐색 하여 구연하였다.

 

 

fun main() {
    val first = readLine()!!.split(" ")
    val m = first[1].toInt()
    val second = readLine()!!.split(" ")
    val set = HashSet<Int>()
    var count = 0
    val parties = ArrayList<List<String>>()
    val visited = arrayOfNulls<Boolean>(m)
    for (i in 1 until second.size) {
        set.add(second[i].toInt())
    }

    for (i in 0 until m) {
        parties.add(readLine()!!.split(" "))
        visited[i] = false
    }

    while (true) { //위 for문에서 한번 검색 가능하지만 편의상
        var con = true
        for (i in 0 until m) {
            if (!visited[i]!!) { //방문 여부 체크
                val partyMember = parties[i]
                for (j in 1 until partyMember.size) {
                    if (set.contains(partyMember[j].toInt())) { //파티에 진실을 아는 사람이 있는지 체크
                        visited[i] = true
                        break
                    }
                }
                if (visited[i]!!) {
                    for (j in 1 until partyMember.size) { 
                        set.add(partyMember[j].toInt()) //파티에 진실을 아는 사람이 있을 경우 전부 추가해준다.
                    }
                    con = false //추가가 되었다면 추가된 사람들로 인해 다른 파티에서 진실을 알 수 있기 때문에 계속 여부
                }
            }
        }

        if (con) {
            for (i in 0 until m) {
                if (!visited[i]!!) {
                    count++
                }
            }
            break
        }
    }

    println(count)
}