[baekjoon] #10216: Count Circle Groups

문제링크

Disjoint Set

• Brute-Force
• If the distance between enemies is smaller than the sum of each enemy's range, union each parent.
• Then, find the number of group using map. It means count how many distinct parent it has.

import kotlin.math.pow

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

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val t = br.readLine().toInt()
    for (i in 0 until t) {
        val n = br.readLine().toInt()
        val enemies = mutableListOf<Enemy>()
        for (j in 0 until n) {
            val (x, y, r) = br.readLine().split(" ").map { it.toInt() }
            enemies.add(Enemy(x, y, r))
        }
        val parent = Array(n) { it }
        for (j in 0 until n) {
            for (k in j + 1 until n) {
                if (isCommunicatable(enemies[j], enemies[k])) {
                    union(parent, j, k)
                }
            }
        }

        var answer = 0
        val counter = mutableMapOf<Int, Int>()
        for (j in 0 until n) {
            val parentJ = find(parent, j)
            if (!counter.containsKey(parentJ)) {
                counter[parentJ] = 1
                answer++
            }
        }
        bw.write("$answer\n")
    }

    br.close()
    bw.close()
}

fun isCommunicatable(enemy1: Enemy, enemy2: Enemy): Boolean {
    val distance = (enemy1.x - enemy2.x).toDouble().pow(2.0) + (enemy1.y - enemy2.y).toDouble().pow(2.0)
    return distance <= (enemy1.r + enemy2.r).toDouble().pow(2.0)
}

fun find(parent: Array<Int>, x: Int): Int {
    if (x == parent[x]) return x
    parent[x] = find(parent, parent[x])
    return parent[x]
}

fun union(parent: Array<Int>, x: Int, y: Int) {
    val parentX = find(parent, x)
    val parentY = find(parent, y)
    if (parentX != parentY) {
        parent[parentY] = parentX
    }
}

Time Complexity

O(n^2)

DFS

• If there is not visited enemy, do dfs search.
• During DFS, check the enemy is visited first.
• Then, check whether the next enemy is not visited and communicatable.
• After DFS search, count up answer variable. It means the number of group.

import kotlin.math.pow

data class Enemy(val x: Int, val y: Int, val r: Int)
fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val t = br.readLine().toInt()
    for (i in 0 until t) {
        val n = br.readLine().toInt()
        val enemies = mutableListOf<Enemy>()
        for (j in 0 until n) {
            val (x, y, r) = br.readLine().split(" ").map { it.toInt() }
            enemies.add(Enemy(x, y, r))
        }
        val visited = Array(n) { false }
        var answer = 0
        for (j in 0 until n) {
            if (!visited[j]) {
                dfs(enemies, visited, j)
                answer++
            }
        }
        bw.write("$answer\n")
    }

    br.close()
    bw.close()
}

fun dfs(enemies: MutableList<Enemy>, visited: Array<Boolean>, curr: Int) {
    visited[curr] = true
    for (next in enemies.indices) {
        if (!visited[next] && isCommunicatable(enemies[curr], enemies[next])) {
            dfs(enemies, visited, next)
        }
    }
}

fun isCommunicatable(enemy1: Enemy, enemy2: Enemy): Boolean {
    val distance = (enemy1.x - enemy2.x).toDouble().pow(2.0) + (enemy1.y - enemy2.y).toDouble().pow(2.0)
    return distance <= (enemy1.r + enemy2.r).toDouble().pow(2.0)
}

Time Complexity

O(n^2)