[백준/BOJ] 1368번: 물대기

문제

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

1368번: 물대기

해설

논에 물을 대는 방법은 두 가지가 있다.

1. 직접 논에 우물을 판다.
2. 이미 물을 대고 있는 다른 논으로부터 물을 끌어온다.

즉, 논에 우물을 파는 비용과 논 사이를 연결하는 하는 비용을 비교해야 하는 문제이다.

 

어렵게 생각할 것 없이, 우물을 파는 비용을 담는 정보도 간선에 추가해주면 된다.

즉, 노드를 한개 더 만든다 생각하면 된다.

 

예를 들어, 문제의 예시를 보자.

첫번째 논을 보면, 첫번째 논과 j번째 논을 열결하는 비용은 0 2 2 2이다.

이 때, 우물을 만드는 비용을 추가해주는 것이다.

우물을 파는 비용은 5이므로, 5 0 2 2 2로 하든, 0 2 2 2 5로 하든 상관없다.

이처럼 모든 논에 대해 우물을 파는 비용을 추가해줬다면, 전형적인 크루스칼 알고리즘을 수행하면 된다.

소스 코드

import java.util.*

private lateinit var map: Array<IntArray>
private lateinit var parent: IntArray

data class Info(val y: Int, val x: Int, val cost: Int): Comparable<Info> {
    override fun compareTo(other: Info): Int  = cost - other.cost
}

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    parent = IntArray(n + 1)
    repeat(n + 1) { i -> parent[i] = i }

    val pq = PriorityQueue<Info>()
    repeat(n) { i ->
        pq.add(Info(0, i + 1, readLine().toInt()))
    }

    for(i in 1 .. n) {
        val st = StringTokenizer(readLine())
        for(j in 1 .. n) {
            var cost = st.nextToken().toInt()
            if(i != j) pq.add(Info(i, j, cost))
        }
    }

    var ans = 0
    while(pq.isNotEmpty()) {
        val cur = pq.poll()

        if(find(cur.y) != find(cur.x)) {
            union(cur.y, cur.x)
            ans += cur.cost
        }
    }

    println(ans)
}

private fun union(a: Int, b: Int) {
    val aParent = find(a)
    val bParent = find(b)

    parent[bParent] = aParent
}

private fun find(node: Int): Int {
    if(parent[node] != node) parent[node] = find(parent[node])
    return parent[node]
}