[알고리즘] 서로소 집합 만들기 - 유니온 파인드 알고리즘 (백준 1043 - Kotlin)

서로소 집합이란?

출처 : 위키백과

위처럼 집합간의 공통원소가 없는 집합을 말한다.

서로소 집합을 구하기 위해 노드를 합치는 연산 (유니온), 노드의 루트 노드를 찾는 연산 (파인드)

을 활용하는 유니온 파인드 알고리즘을 사용할 수 있다.

 

파인드 (Find) - 노드의 루트 노드 찾기

1. 원소 각각의 부모 노드를 저장할 배열을 생성하고 자기 자신으로 초기화 한다.
2. 최상위 노드에 도달할 때 까지 자기 자신의 부모 노드를 탐색한다.
3. 위 과정에서 포함된 노드들의 부모를 전부 최상위 노드로 바꿔준다.

val parent = Array(n + 1) {it}

fun find(x: Int): Int{
    return if (x == parent[x]) x
    else {
        parent[x] = find(parent[x])
        parent[x]
    }
}

 

유니온 (Union) - 두 노드 합치기

1. 두 노드에 대해 Find 연산을 진행하여 두 노드의 부모 노드 정보를 얻는다.
2. 두 부모 노드 정보를 비교하여 같지 않을 경우 같도록 하여 같은 집합에 속하도록 한다.

fun union(x: Int, y: Int){
    val nx = find(x)
    val ny = find(y)

    if(nx != ny){
        parent[ny] = nx
    }
}

 

예제 코드 (백준 1043)

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

1043번: 거짓말

// [백준] 1043. 거짓말 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var parent: Array<Int>

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    
    val (n,m) = readLine().split(" ").map { it.toInt() } // 사람의 수, 파티의 수
    val arr = Array(n + 1) {false} // 진실 아는 사람
    var st = StringTokenizer(readLine())

    val party = Array (m) { arrayListOf<Int>() } // 파티 참여 인원 정보
    parent = Array(n + 1) {it} // 부모 정보

    val trueN = st.nextToken().toInt() // 진실을 아는 사람 수
    // 진실을 아는 사람
    repeat(trueN){
        val tmp = st.nextToken().toInt()
        arr[tmp] = true
    }

    // 파티 정보
    for(i in 0 until m){
        st = StringTokenizer(readLine())

        val pn = st.nextToken().toInt() // 파티 인원수

        for(j in 0 until pn){
            party[i].add(st.nextToken().toInt())

            // 파티 참여 인원들의 부모노드를 같게함
            if (j > 0) union(party[i][j], party[i][j - 1])
        }
    }

    for(i in 1 .. n){
        if(arr[i]){
            // 진실을 아는 사람 부모 정보
            val par = find(i)

            // 전체 탐색, 부모가 같다면 진실을 아는 사람에 추가
            for(j in 1 .. n){
                if(par == find(j)){
                    arr[j] = true
                }
            }
        }
    }

    val trueList = arrayListOf<Int>()
    for(i in arr.indices){
        if(arr[i]){
            trueList.add(i)
        }
    }

    var result = m
    for(i in 0 until m){
        // 파티 인원 중 진실을 아는 사람이 있다면 진실을 아는 파티
        for(j in party[i]){
            if(trueList.contains(j)){
                result--
                break
            }
        }
    }

    println(result)
}


fun union(x: Int, y: Int){
    val nx = find(x)
    val ny = find(y)

    if(nx != ny){
        parent[ny] = nx
    }
}

// 최상위 노드 찾기
fun find(x: Int): Int{
    return if (x == parent[x]) x
    else {
        parent[x] = find(parent[x])
        parent[x]
    }
}