코틀린 코딩테스트 강좌, 유니온 파인드

안녕하세요! 이번 글에서는 코틀린을 사용하여 유니온 파인드(Union-Find) 알고리즘에 대해 살펴보겠습니다. 유니온 파인드는 집합 데이터 구조를 효율적으로 관리하는 방법으로, 주로 연결된 컴포넌트를 찾고 결합하는 데 사용됩니다. 이 알고리즘은 그래프 이론과 관련된 문제에서 종종 사용되는 중요한 개념입니다.

문제 설명

다음은 유니온 파인드를 이용하여 해결할 수 있는 문제입니다. 연결된 컴포넌트의 개수 세기 문제를 통해 유니온 파인드의 중요성을 이해해 보겠습니다.

문제: 연결된 컴포넌트의 개수

당신은 N개의 노드와 M개의 간선이 있는 그래프를 가지고 있습니다. 각 노드는 1부터 N까지 번호가 매겨져 있습니다. 다음과 같이 M개의 간선이 주어질 때, 연결된 컴포넌트의 개수를 구하는 프로그램을 작성하세요.

입력 형식

N M
u1 v1
u2 v2
...
uM vM

여기서 N은 노드의 개수, M은 간선의 개수이며, u_i와 v_i는 i번째 간선의 양 끝 점을 나타냅니다.

출력 형식

연결된 컴포넌트의 개수를 한 줄에 출력합니다.

예제

입력:
5 3
1 2
2 3
4 5

출력:
2

예제에서 주어진 그래프를 살펴보면, 노드 1, 2, 3이 하나의 연결된 컴포넌트를 이루고, 노드 4, 5가 또 하나의 연결된 컴포넌트를 이루므로 총 2개의 연결된 컴포넌트가 존재합니다.

유니온 파인드 알고리즘 소개

유니온 파인드(Union-Find) 또는 분리 집합(Disjoint Set Union) 자료 구조는 다음과 같은 두 가지 주요 연산을 지원합니다:

Find: 특정 원소가 속한 집합의 대표 원소를 찾습니다.
Union: 두 개의 집합을 하나로 합칩니다.

유니온 파인드는 주로 비연결 그래프의 연결성을 관리하기 위해 사용되며, 효율성을 위해 경로 압축(Path Compression)과 합치기 기준(Union by Rank) 기법을 사용합니다. 이러한 기법들은 합친 후에 트리 형태로 구조를 유지함으로써 ‘Find’ 연산을 빠르게 수행할 수 있도록 돕습니다.

코틀린으로 구현하기

이제 유니온 파인드를 코틀린으로 구현해 보겠습니다. 아래는 위 문제를 해결하기 위한 코드입니다.

class UnionFind(val size: Int) {
    private val parent = IntArray(size + 1) { it } // 각 노드의 부모를 자기 자신으로 초기화
    private val rank = IntArray(size + 1) { 1 } // 각 집합의 랭크 초기화

    // Find 연산: 경로 압축 기법
    fun find(node: Int): Int {
        if (parent[node] != node) {
            parent[node] = find(parent[node]) // 부모를 재귀적으로 찾으면서 경로를 압축
        }
        return parent[node]
    }

    // Union 연산: 랭크를 기준으로 집합을 합침
    fun union(node1: Int, node2: Int) {
        val root1 = find(node1)
        val root2 = find(node2)

        if (root1 != root2) {
            if (rank[root1] > rank[root2]) {
                parent[root2] = root1
            } else if (rank[root1] < rank[root2]) {
                parent[root1] = root2
            } else {
                parent[root2] = root1
                rank[root1]++
            }
        }
    }

    // 연결된 컴포넌트의 개수 세기
    fun countComponents(): Int {
        val rootSet = mutableSetOf()
        for (i in 1..size) {
            rootSet.add(find(i)) // 각 노드의 루트를 찾아 집합에 추가
        }
        return rootSet.size // 유일한 루트의 개수가 연결된 컴포넌트의 개수
    }
}

fun main() {
    val reader = System.`in`.bufferedReader()
    val (n, m) = reader.readLine().split(" ").map { it.toInt() }
    val unionFind = UnionFind(n)

    for (i in 0 until m) {
        val (u, v) = reader.readLine().split(" ").map { it.toInt() }
        unionFind.union(u, v) // 간선 정보로 두 노드를 합침
    }

    println(unionFind.countComponents()) // 연결된 컴포넌트 개수 출력
}

코드 설명

위 코드는 유니온 파인드 자료 구조를 구현한 것입니다. 각 노드의 부모를 저장하기 위해 parent 배열을 사용하고, 각 집합의 랭크(높이)를 저장하기 위해 rank 배열을 사용합니다.

1. Find 메서드는 경로 압축을 통해 해당 노드의 루트를 재귀적으로 찾아갑니다. 이 과정에서 모든 노드가 직접 루트를 가리키게 하여 향후 탐색을 빠르게 합니다.

2. Union 메서드는 두 개의 노드의 루트를 찾아, 랭크를 비교하여 더 낮은 랭크를 가진 집합이 높은 랭크를 가진 집합에 연결되도록 합니다. 만약 랭크가 동일한 경우, 하나의 집합을 다른 집합의 루트에 연결하고 랭크를 증가시킵니다.

3. countComponents 메서드는 모든 노드에 대해 루트를 찾아 유일한 루트의 개수를 계산함으로써 연결된 컴포넌트의 개수를 반환합니다.

시간 복잡도 분석

유니온 파인드의 각 연산은 매우 빠르며, 거의 상수 시간에 수행할 수 있습니다. 이 알고리즘의 평균 시간 복잡도는 다음과 같습니다:

Find: O(α(N))
Union: O(α(N))

α(N)는 아커만 함수의 역함수이며, 이는 매우 느리게 성장하는 함수입니다. 따라서 유니온 파인드는 대규모 데이터에서도 효율적으로 작동합니다.

마무리

이번 글에서는 유니온 파인드 알고리즘의 기초 개념과 활용을 통해, 연결된 그래프의 문제를 해결하는 방법에 대해 배웠습니다. 코틀린을 이용한 구현을 통해 이론뿐만 아니라 실습도 병행할 수 있었는데, 이는 코딩 테스트 준비에 큰 도움이 될 것입니다.

유니온 파인드는 다양한 분야에서 사용될 수 있는 중요한 알고리즘이므로, 반드시 숙지하시기를 권장합니다. 추후 다른 알고리즘과 자료 구조에 대한 강좌도 이어질 예정이니 많은 관심 부탁드립니다!