1414번: 불우이웃돕기

문제 출처 : https://www.acmicpc.net/problem/1414

1414번: 불우이웃돕기

언어 : Kotlin

 

문제 설명 :

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.
다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

 

출력 :

첫째 줄에 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력한다. 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
3 abc def ghi	40
2 a0 0b	-1
4 0X00 00Y0 0000 00Z0	0
2 Az aZ	105
4 0top c0od er0o pen0	134

 

다른 사람의 풀이 : 

https://uknowblog.tistory.com/297

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

 

최소 스패닝 트리 문제.

랜선을 가장 많이 기부할 수 있는 길이를 찾는 문제로, 다솜이가 쓸 랜선은 냅두고 남은 랜선을 줘야한다.

컴퓨터는 연결된 다른 컴퓨터를 타고 들어가 네트워크를 사용할 수 있으므로, 전체 랜선의 길이에서 최소 스패닝 트리의 가중치의 합을 빼면 된다.

 

최소 스패닝 트리:

https://uknowblog.tistory.com/294

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

 

랜선의 길이는 알파벳으로 주어진다.

a ~ z = 1 ~ 26

A ~ Z = 27 ~ 52

아스키코드를 사용해 나올 숫자를 좀 조정해주면 된다.

 

해당 풀이를 작성한 사람은 크루스칼 알고리즘을 사용했다고 한다.

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

 

길이가 O보다 큰 간선을 모두 우선순위 큐에 넣고, 큐에서 하나씩 빼며 두 노드가 서로 이어져있지 않다면 (부모가 다르다면) union을 통해 서로 같게 만든 뒤, 총 랜선의 길이에서 현재 랜선의 길이를 뺀다.

 

또는 모든 컴퓨터가 연결되어있지 않은 경우 "-1"을 출력하고 끝내는 것이 존재하는데, 이 경우 첫번째 컴퓨터의 부모와 다른 컴퓨터의 부모가 같은지 확인하여 스패닝 트리가 되는지를 판단한다. 하나라도 첫번째 컴퓨터의 부모와 다르다면 스패닝 트리가 만들어질 수 없으므로 "-1"을 출력하고 빠져나간다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.system.exitProcess

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

lateinit var arr: Array<Int>

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    arr = Array(n + 1) { it }

    val map = Array(n) {
        val line = readLine()
        Array(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)) {
            bw.write("-1")
            bw.flush()
            exitProcess(0)
        }
    }

    bw.write("$total")
    bw.flush()
    bw.close()
}

fun find(x: Int): Int = if (x == arr[x]) x else { arr[x] = find(arr[x]); arr[x] }

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

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