[백준] 4195번: 친구 네트워크 - Kotlin[코틀린]

문제

 

4195번: 친구 네트워크

 

---

풀이

 

 입력된 친구 관계를 해시맵과 유니온 파인드(Union-Find)을 활용해 풀이하면 된다. 해시맵은 <String, Int>형으로 선언하여 이름과 이름에 대한 번호를 대응시킨다. 이름을 입력받을 때마다 해시맵에 없다면 새로운 번호를 할당한다. 이 번호는 유니온 파인드에서 각 노드의 루트 노드가 된다.

 

 유니온 파인드에서는 루트 노드를 저장하는 배열과 해당 그룹에 속한 친구들의 수를 저장하는 배열을 같이 이용한다. 합집합 연산을 통해 루트 노드를 변경해주고 그에 따라 친구의 수를 합쳐주면 된다.

 

 입력받은 이름들을 유니온 연산하고 그룹별로 친구들의 수를 출력해주면 된다.

 

---

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    lateinit var parent: IntArray // 루트 노드
    lateinit var friends: IntArray // 친구의 수

    fun find(a: Int): Int {
        return if(a == parent[a]) a
        else {
            parent[a] = find(parent[a])
            parent[a]
        }
    }
    fun union(a: Int, b: Int) : Int {
        val x = find(a)
        val y = find(b)

        if(x!=y) {
            parent[y] = x
            friends[x] += friends[y]
        }
        return friends[x]
    }

    val sb = StringBuilder()
    repeat(br.readLine().toInt()) {
        val num = br.readLine().toInt()
        parent = IntArray(num*2){ it }
        friends = IntArray(num*2){ 1 }

        val hashMap = HashMap<String, Int>()
        var idx = 0 // 번호
        for(i in 0 until num) {
            val st = StringTokenizer(br.readLine())
            val a = st.nextToken()
            val b = st.nextToken()

            if(!hashMap.containsKey(a)) {
                hashMap[a] = idx++
            }
            if(!hashMap.containsKey(b)) {
                hashMap[b] = idx++
            }

            sb.append("${union(hashMap[a]!!, hashMap[b]!!)}\n")
        }
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}