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

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

1717번: 집합의 표현

 

난이도 : 골드 4
태그 : 자료 구조, 분리 집합

 

 

설명

0 a b 일때는 a와 b를 합집합하고,

1 a b 일때는 a와 b가 같은 집합에 속하는지 확인하는 문제입니다.

 

즉, 원소들간에 그룹을 만들고, 그룹을 하나씩 합쳐가며,

1 연산일때 두 원소가 같은 그룹 내에 존재하는지 확인하면 됩니다.

 

해당 문제는 분리 집합과 Union - Find 알고리즘을 사용하면 쉽게 구현할 수 있습니다.

 

 

분리집합

분리집합은 서로소 집합이라고도 불립니다.

 

분리, 서로소라는 이름에서 알 수 있듯이,

 

각각의 집합이 공통원소를 가지지 않는 집합입니다.

 

즉, 전체 집합 U에 대해 두개의 집합 A, B가 있을 때,

A ∩ B = Ø 가 성립합니다.

이는 집합이 두개가 아닌 세개 이상일 경우에도 마찬가지로, 각 집합이 공통원소를 가지지 않습니다.

 

 

Union - Find 

분리집합은 트리 형태로 나타낼 수 있습니다.

 

각 노드의 부모 번호를 기억하며, 최상위 노드(루트)가 같을 경우 같은 집합으로 봅니다.

 

 

아래는 각 노드의 부모를 넣는 배열입니다.

var parent: Array<Int>

 

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

find 알고리즘은 해당 노드의 루트노드를 찾는 함수입니다.

 

노드 x에 대해 자기 자신(x)와 자신의 부모 노드(parent[x])가 같을 경우,

이는 최상위 노드인 루트 노드이며, x를 그대로 리턴하면 됩니다.

 

만약 x와 부모노드가 같지 않다면, 이는 타 노드의 자식노드인 경우로,

parent[x]에 대해 재귀적으로 find를 진행합니다.

 

 

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

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

union 메소드는

각 노드 x, y의 부모노드를 찾고,

부모노드가 같지 않을 경우 트리를 병합하는 작업을 수행하는 함수입니다.

 

 

 

 

소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

lateinit var parent: Array<Int>

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()

    val nm = br.readLine().split(" ")
    val n = nm[0].toInt()
    val m = nm[1].toInt()

    // 각 원소의 부모
    parent = Array(n + 1) { it }

    repeat(m) {
        val st = StringTokenizer(br.readLine())
        // 0 a b -> a, b 합집합
        // 1 a b -> a, b 같은 집합인지 확인

        val oper = st.nextToken().toInt() // 연산자
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()

        // 0 연산 (합집합) -> union
        if(oper == 0) {
            union(a, b)
        } else {
            // 1 연산 (같은 집합에 속하는지) -> 부모가 같은지 확인
            if(find(a) == find(b)) {
                sb.append("YES\n")
            } else {
                sb.append("NO\n")
            }
        }
    }
    print(sb)
}

// 원소의 부모를 찾는 과정
// x와 x의 부모가 같음 (부모가 자기 자신) -> 반환
// x와 x의 부모가 다름 -> x의 부모를 매개변수로 재귀적으로 수행
fun find(x: Int): Int {
    return if (parent[x] == x) x
    else {
        parent[x] = find(parent[x])
        parent[x]
    }
}

// 두 원소의 부모를 찾고, 둘이 같게 만들어줌
fun union(x: Int, y: Int) {
    val nx = find(x)
    val ny = find(y)

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

 

 

 

후기

 

기존에 포스팅했던 백준 1043번 '거짓말' 문제와 비슷한 분리집합 문제입니다.

분리집합에 대한 설명은 이전에 포스팅했던 설명을 가져왔습니다.

 

 

https://uknowblog.tistory.com/43

[백준 1043번][Kotlin] 거짓말 (분리집합, Union-Find 사용)