[백준][Kotlin]1717번 집합의 표현

해당문제는 유니온 파인드를 이용하여 작성하면 통과할 수 있는 문제였습니다.

 

유니온 파인드(Union-Find)는 서로소 집합(Disjoint-set)을 표현하고 관리하기 위한 알고리즘입니다.

서로소 집합은 공통 원소가 없는 두 집합을 의미합니다. 예를 들어, {1, 2, 3}과 {4, 5}는 서로소 집합입니다.

유니온 파인드 알고리즘은 각 원소를 개별적인 집합으로 만들고, 두 개의 집합을 하나로 합치는(union) 연산과 어떤 원소가 어떤 집합에 포함되어 있는지를 확인하는(find) 연산을 지원합니다.

유니온 파인드 알고리즘은 배열 형태로 구현되며, 배열의 각 인덱스는 각각의 원소를 의미합니다. 각 원소는 자신이 속한 집합의 대표 원소(루트 노드)를 가리키는 포인터를 갖습니다.

두 집합을 합치는 경우, 각 집합의 대표 원소를 찾아 비교한 후, 하나의 집합의 대표 원소가 다른 집합의 대표 원소를 가리키도록 합니다. 이를 "Union by rank"나 "Union by size" 방식으로 구현할 수 있습니다.

원소가 어떤 집합에 속해 있는지를 확인하는 경우, 해당 원소의 대표 원소를 찾아 반환합니다. 이 과정에서 경로 압축(Path Compression)을 적용하여, 한 번 찾은 대표 원소를 다시 찾을 때의 시간을 줄일 수 있습니다.

유니온 파인드 알고리즘의 시간 복잡도는 일반적으로 O(mα(n))입니다. 여기서 m은 연산의 수, n은 원소의 수를 의미하며, α는 역 Ackermann 함수의 역함수로, 거의 모든 상황에서 4보다 작은 값을 가집니다. 따라서, 유니온 파인드 알고리즘은 대부분의 상황에서 매우 효율적으로 동작합니다.

 

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

 

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

lateinit var arr: 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())
    var n = st.nextToken().toInt()
    var m = st.nextToken().toInt()

    arr = IntArray(n+1){i: Int ->  i}
    repeat(m){
        st = StringTokenizer(br.readLine())
        var operation = st.nextToken().toInt() // 0일 경우 합집합, 1일 경우 포함되어있는지 확인
        var a = st.nextToken().toInt() // 대표 노드
        var b = st.nextToken().toInt() // 자식 노드
        when(operation){
            0 -> union(a,b)
            1 -> check(a,b)
        }
    }

    bw.flush()
    bw.close()
}

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

fun find(a:Int):Int{
    if(a != arr[a]){
        arr[a] = find(arr[a])
    }
    return arr[a]
}

fun check(a:Int,b:Int){
    if(find(a) == find(b)) bw.appendLine("YES")
    else bw.appendLine("NO")
}