[백준] 26. 별자리 만들기 4386 해설

별자리 만들기

4386번: 별자리 만들기

 

문제

 

풀이

높은 정답 비율답게 쉽게 풀 수 있었던 문제입니다.

결국에는 최소 비용으로 별자리를 이어주면 되기 때문에 최소 간선만을 이어줘야 되며 사이클이 생기면 안 됩니다. 따라서 최소 신장 트리 알고리즘을 사용하면 되는 문제입니다.

 

다만 간선이 따로 주어지지 않았기 때문에 각 별자리의 좌표를 이용하여 모든 경우의 간선을 구해주면 됩니다.

 

먼저 크루스칼을 이용한 풀이입니다.

1. 모든 간선을 구한 뒤 우선순위 큐에 넣어줍니다.
2. 그다음 큐에서 간선을 하나씩 빼주면서 union-find을 이용하여 사이클 여부를 확인해 줍니다.
3. 사이클이 생기지 않을 경우에만 결과값에 간선을 추가해 줍니다.

import java.io.StreamTokenizer
import java.util.PriorityQueue

data class Node(val x: Double, val y: Double)
data class Edge(val n1: Int, val n2: Int, val dist: Double)
lateinit var parents: IntArray
lateinit var rank: IntArray

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Double {
        nextToken()
        return nval
    }

    fun find(num : Int) : Int {
        if (parents[num] == num) {
            return num
        }
        return find(parents[num])
    }

    fun unionFind(n1: Int, n2: Int) : Boolean {
        val p1 = find(n1)
        val p2 = find(n2)

        if (p1 == p2) return false
        if (rank[p1] == rank[p2]) rank[p1]++

        if (rank[p1] > rank[p2]) {
            parents[p2] = p1
        } else {
            parents[p1] = p2
        }
        return true
    }

    val N = input().toInt()

    val nodes = Array(N) {Node(0.0, 0.0)}
    val pq = PriorityQueue<Edge>(compareBy { it.dist })
    parents = IntArray(N){it}
    rank = IntArray(N)

    repeat(N) { i ->
        nodes[i] = Node(input(), input())
    }

    // 두 정점을 잇는 모든 간선을 구한다.
    for (i in 0 until N-1) {
        for (j in i+1 until N) {
            pq.add(Edge(i, j, calEdge(nodes[i], nodes[j])))
        }
    }

    var result = 0.0
    var count = N-1
    while (pq.isNotEmpty()) {
        val edge = pq.poll()

        // 사이클이 생기지 않는 경우 결과값에 추가
        if (unionFind(edge.n1, edge.n2)) {
            result += edge.dist
            count--
        }
        if (count == 0) break
    }

    print(String.format("%.2f", result))
}

// 두 점 사이의 거리
private fun calEdge(n1: Node, n2: Node): Double {
    return Math.sqrt(Math.pow(n1.x - n2.x, 2.0) + Math.pow(n1.y - n2.y, 2.0))
}

 

 

프림을 이용한 풀이입니다.

1. 노드 별 거리를 이중 배열에 담아줍니다.
2. 시작 노드를 설정해 준 뒤 우선순위 큐에 담아줍니다.
3. 노드의 인접 노드 중 방문하지 않은 노드를 모두 우선순위 큐에 담아줍니다.
4. 모든 노드를 방문할 때까지 3번을 반복해 줍니다.

import java.io.StreamTokenizer
import java.util.PriorityQueue

data class Node(val x: Double, val y: Double)
data class Edge2(val n: Int, val dist: Double)

fun 별자리만들기_프림풀이()  = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Double {
        nextToken()
        return nval
    }

    val N = input().toInt()
    val nodes = Array(N) {Node(0.0,0.0)}
    val arr = Array(N) { DoubleArray(N) }
    repeat(N) { i ->
        nodes[i] = Node(input(), input())
    }

	// 각 별 자리의 간선을 이중 배열에 담아준다.
    for (i in 0 until N-1) {
        for (j in i+1 until N) {
            val dist = calEdge(nodes[i], nodes[j])
            arr[i][j] = dist
            arr[j][i] = dist
        }
    }

    var result = 0.0
    val visited = BooleanArray(N)
    val pq = PriorityQueue<Edge2>(compareBy { it.dist })
    pq.add(Edge2(0,0.0))  // 시작 노드 설정

    while (pq.isNotEmpty()) {
        val cur = pq.poll()

        if (visited[cur.n]) continue
        visited[cur.n] = true
        result += cur.dist

        // 인접한 노드를 우선순위 큐에 담아준다.
        for (next in 0 until N) {
            if (!visited[next]) {
                pq.add(Edge2(next, arr[cur.n][next]))
            }
        }
    }
    print(String.format("%.2f", result))
}

// 두 점 사이의 거리
private fun calEdge(n1: Node, n2: Node): Double {
    return Math.sqrt(Math.pow(n1.x - n2.x, 2.0) + Math.pow(n1.y - n2.y, 2.0))
}