[백준 13418번] [Kotlin] 학교 탐방하기

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

13418번: 학교 탐방하기

 

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

 

 

설명

최소 스패닝 트리를 응용하여 각 간선의 최소값을 구하면서,

최대 스패닝 트리를 구해 각 간선의 최댓값을 구하는 문제입니다.

최대 스패닝 트리의 경우, 최소 스패닝 트리에서 단순히 정렬 조건만 반대로 지정하여 한 번 더 수행하면 구할 수 있습니다.

 

최소 스패닝 트리를 잘 모르신다면 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/294

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

 

해당 문제에서 저는 유니온파인드를 사용한 크루스칼 알고리즘을 사용해 풀이하였습니다.

 

 

 

소스코드

import java.util.PriorityQueue
import java.util.StringTokenizer

data class Edge(val from: Int, val to: Int, val weight: Int)

lateinit var parent: Array<Int>

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }

    val upPq = PriorityQueue<Edge> { o1, o2 -> o2.weight - o1.weight }
    val downPq = PriorityQueue<Edge> { o1, o2 -> o1.weight - o2.weight }

    repeat(m + 1) {
        val st = StringTokenizer(readLine())
        var (from, to, weight) = Array(3) { st.nextToken().toInt() }
        weight = if (weight == 1) 0 else 1 // 입력으로 0이 주어지면 오르막길, 1이 주어지면 내리막길이다!!!!!!
        upPq.offer(Edge(from, to, weight))
        downPq.offer(Edge(from, to, weight))
    }

    parent = Array(n + 1) { it }

    var max = 0
    var min = 0

    while (upPq.isNotEmpty()) {
        val target = upPq.poll()
        if (union(target.to, target.from)) max += target.weight
    }

    parent = Array(n + 1) { it }

    while (downPq.isNotEmpty()) {
        val target = downPq.poll()
        if (union(target.to, target.from)) min += target.weight
    }

    println(max * max - min * min)
}


fun find(x: Int): Int {
    return if (x == parent[x]) x
    else {
        parent[x] = find(parent[x])
        return 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
}

 

 

아래 코드는 내림차순으로 정렬하여 오르막길을 최대로 할 때 쓰이는 우선순위 큐 입니다. (최대 스패닝 트리)

val upPq = PriorityQueue<Edge> { o1, o2 -> o2.weight - o1.weight }

 

아래 코드는 오름차순으로 정렬하여 오르막길을 최소로 할 때 쓰이는 우선순위 큐 입니다. (최소 스패닝 트리)

val downPq = PriorityQueue<Edge> { o1, o2 -> o1.weight - o2.weight }

 

위 두 가지의 큐를 각각 넣어준 뒤, 최소/최대 스패닝 트리 알고리즘을 수행하면 간선의 최소, 최대 가중치를 구할 수 있습니다.

저는 오르막길을 1, 내리막길을 0 으로 설정하여 가중치 합에 그대로 더해주었습니다.

피로도의 계산은 (오르막길의 개수)^2 이니, 내리막길을 0 으로 하면 단순히 (가중치의 합)^2 = (오르막길 개수의 합)^2 이기 때문입니다.

 

 

이 문제를 풀 때 가장 실수하기 쉬운 부분이 있습니다.

0이 오르막길! 1이 내리막길 입니다!!!

저는 그냥 단순히 오르막길이 1일 거라 생각해 1이든 0이든 간선의 가중치 총 합에 더한 뒤 구하면 되겠다 생각을 했는데, 반대였습니다...

예제는 1이 오르막길 이던 내리막길 이던 동일하게 나옵니다.

 

 

 

후기

오르막길 입력이 0으로 주어지는 걸 잘 보지 않고 맞는데 왜 틀림??? 을 외치던 문제였습니다.

역시 문제 풀 땐 지문을 꼼꼼히 봐야합니다.