[백준 10216번] [Kotlin] Count Circle Groups

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

10216번: Count Circle Groups

 

난이도 : 골드 4
태그 : 자료 구조, 그래프 이론, 그래프 탐색, 기하학, 분리 집합

 

 

설명

통신 범위가 직/간접적으로 겹치는 부대는 하나의 부대처럼 행동합니다.

즉, 통신범위가 겹치는 그룹을 모두 같은 그룹으로 묶어 몇 개의 그룹이 나오는지 구하는 문제입니다.

 

그룹화와 서로 다른 그룹의 개수를 구한다는 점에서

분리집합과 유니온 파인드를 사용할 수 있을 것 같습니다.

 

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

서로 겹치지 않는 원소를 가지고 있는 집합이지요.

자세한 내용은 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/61

[자료구조] 분리 집합(Disjoint set)과 유니온 - 파인드(Union-Find)

 

 

유니온 - 파인드 알고리즘을 사용하여

통신 범위가 겹치는 두 그룹끼리 서로 같은 그룹으로 묶어줌으로써

최종적으로 우리는 서로 다른 그룹을 알아낼 수 있습니다.

 

그렇다면, 서로간의 통신이 겹치는지는 어떻게 확인할 수 있을까요?

통신 범위는 특정 좌표 (x, y)를 기준으로 반지름 r 만큼의 원의 범위입니다.

 

 

d = root ( (x1 - x2) ^ 2 + (y1 - y2) ^ 2) )

두 원 간의 중심의 거리(d)는 피타고라스로 쉽게 구할 수 있습니다.

두 원의 중심의 거리 d가 r1 + r2 보다 클 경우, 두 그룹은 서로 통신할 수 없습니다.

 

 

 

 

반면의 두 원의 중심 사이의 거리(d)가 두 원의 반지름의 합(r1+r2) 보다 작거나 같다면

두 원은 서로 접하거나 겹치는 부분이 생기며 한 그룹으로 합쳐집니다.

즉, d <= r1 + r2 일 때, 두 그룹은 서로 같은 그룹이 됩니다.

 

 

 

소스코드

package baekjoon.gold.g4.`Count Circle Groups`

import java.util.StringTokenizer
import kotlin.math.pow
import kotlin.math.sqrt

data class Circle(val x: Int, val y: Int, val r: Int)

lateinit var parent: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    
    repeat(readLine().toInt()) {
        val n = readLine().toInt()
        val circles = Array(n) {
            val st = StringTokenizer(readLine())
            Circle(st.nextToken().toInt(), st.nextToken().toInt(), st.nextToken().toInt())
        }

        parent = IntArray(n) { it }

        for (i in 0..<n) {
            for (j in i + 1..<n) {
                if (isConnected(circles[i], circles[j])) union(i, j)
            }
        }

        val parentSet = HashSet<Int>()
        for (i in 0..<n) {
            parentSet.add(find(i))
        }

        sb.appendLine(parentSet.size)
    }

    print(sb)
}

fun isConnected(circle1: Circle, circle2: Circle): Boolean {
    val (x1, y1, r1) = circle1
    val (x2, y2, r2) = circle2

    val d = sqrt((x1 - x2).toDouble().pow(2.0) + (y1 - y2).toDouble().pow(2.0))

    return d <= r1 + r2
}


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

fun union(x: Int, y: Int) {
    val (px, py) = find(x) to find(y)
    parent[py] = px
}

 

여기서 주의할 부분은 서로 다른 그룹의 개수를 카운트하는 부분입니다.

각 통신탑의 최상위 노드(루트) 중,  서로 다른 루트의 개수를 구하는 것인데요.

저는 중복제거를 위해 Set 자료구조를 사용하였습니다.

 

 

 

후기

기하학 + 분리집합이라는 다소 독특한 문제였습니다.

비슷한 문제가 있다면 또 풀어보고 싶네요.