[백준 1414번] [Kotlin] 불우이웃돕기

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

1414번: 불우이웃돕기

 

난이도 : 골드 3
태그 : 그래프이론, 최소 스패닝 트리, 문자열

 

 

설명

몇 가지 기믹이 들어간 최소 스패닝 트리 문제입니다.

 

해당 문제는 랜선을 가장 많이 기부할 수 있는 길이를 찾는 문제입니다.

따라서, 다솜이가 쓸 랜선은 냅두고, 남은 랜선을 줘야 하는데요.

컴퓨터는 연결된 다른 컴퓨터를 타고 들어가 네트워크를 사용할 수 있으므로,

전체 랜선의 길이에서 최소 스패닝 트리의 가중치의 합을 빼면 되겠습니다.

 

 

최소 스패닝 트리의 경우, 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/294

[알고리즘] 최소 스패닝 트리 (MST, Minimum Spanning Tree)

 

 

 

 

소스코드

import java.util.PriorityQueue
import kotlin.system.exitProcess

data class Edge(val from: Int, val to: Int, val weight: Int) : Comparable<Edge> {
    override fun compareTo(other: Edge): Int {
        return this.weight - other.weight
    }
}

lateinit var parent: Array<Int>

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    parent = Array(n + 1) { it }

    // 0 -> 0, a ~ z -> 1 ~ 26, A ~ Z -> 27 ~ 52
    val map = Array(n) {
        val line = readLine()
        Array<Int>(n) {
            when {
                line[it].isDigit() -> 0
                line[it].isLowerCase() -> line[it] - 'a' + 1
                else -> line[it] - 'A' + 27
            }
        }
    }


    val pq = PriorityQueue<Edge>()

    for (i in 0 until n) {
        for (j in 0 until n) {
            if (map[i][j] > 0) {
                pq.offer(Edge(i, j, map[i][j]))
            }
        }
    }

    var total = map.sumOf { it.sum() }

    while (pq.isNotEmpty()) {
        val target = pq.poll()
        if (union(target.to, target.from)) total -= target.weight
    }

    val firstParent = find(0)
    for (i in 1 until n) {
        if (firstParent != find(i)) {
            println(-1)
            exitProcess(0)
        }
    }

    println(total)
}

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

fun union(x: Int, y: Int): Boolean {
    val nx = find(x)
    val ny = find(y)

    return if (nx != ny) {
        parent[nx] = ny
        true
    } else false
}

 

특이하게도, 입력으로 랜선의 길이가 알파벳으로 주어집니다.

a ~ z는 1 ~ 26이니, (input) - 'a' + 1을 해주면 숫자로 바꿀 수 있을 것 같네요.

A ~ Z는 27 ~ 52이니, (input) - 'A' + 26 + 1을 해주면 숫자로 바꿀 수 있겠죠?

 

저는 해당 문제에서는 크루스칼 알고리즘을 사용하였는데요.

크루스칼 알고리즘은 분리집합과 유니온 - 파인드를 통해 구현할 수 있습니다.

 

길이가 0 보다 큰 간선을 모두 우선순위 큐에 넣고,

큐에서 하나씩 빼며 두 노드가 서로 이어져있지 않다면 (부모다 다르면)

union을 통해 서로 같게 만들어주고, 총 랜선의 길이에서 현재 랜선의 길이를 뺍니다.

 

마지막으로, 모든 컴퓨터가 서로 이어지지 않는 경우도 있습니다. (최소 스패닝 트리가 아예 만들어질 수 없는 경우)

이 경우, 첫 번째 컴퓨터의 부모와 다른 컴퓨터의 부모가 같은지 확인하여 스패닝 트리가 되었는지 판단합니다.

하나라도 첫 번째 컴퓨터의 부모와 다르다면, 해당 셋은 스패닝 트리가 될 수 없습니다.

 

 

후기

가중치의 총 합을 구하는 문제는 많이 봤는데,

모든 간선의 합 - 최소 스패닝 트리의 가중치의 합 문제는 처음 보네요.

 

무엇보다 문자열로 길이를 주는게 좀 신박했던 것 같습니다.