[백준/BOJ] 13418번: 학교 탐방하기

문제

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

13418번: 학교 탐방하기

해설

MST는 최소 신장 트리이다.

즉, 가중치가 가장 낮은 트리를 구하는 것이다.

이는 크루스칼 알고리즘과 프림 알고리즘으로 구할 수 있다.

 

그렇다면 반대로 신장 트리 중 최악의 경우도, 크루스칼 알고리즘과 프림 알고리즘으로 구할 수 있다는 얘기가 된다.

이 문제에서는 (최악일 경우의 피로도 - 최소일 경우의 피로도)를 구해야 한다.

 

나는 입구에서 시작을 해야 한다는 생각으로 프림 알고리즘을 사용하였다.

후에 다른 사람들이 풀은 것을 보니, 어짜피 모든 간선을 최소, 최악으로 구하는 것은 같아 크루스칼 알고리즘으로도 해결할 수 있는 문제였다.

 

최소의 경우는 기본적인 크루스칼 알고리즘과 프림 알고리즘을 따른다.

최악의 경우는 가중치를 거꾸로 뒤집어서 내림차순으로 정렬하여 사용하면 된다.

 

이 문제에서는 오르막길에서 피로도가 쌓이는데,

오르막길이 0으로 표시되고, 내리막길이 1로 표시되는 것에 주의해야한다.

소스 코드

import java.util.*
import kotlin.collections.ArrayList

private lateinit var edge: Array<ArrayList<Pair<Int, Int>>>
private lateinit var visited: BooleanArray

data class Des(val node: Int, val tired: Int): Comparable<Des> {
    override fun compareTo(other: Des): Int = other.tired - tired
}

data class Asc(val node: Int, val tired: Int): Comparable<Asc> {
    override fun compareTo(other: Asc): Int = tired - other.tired
}

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

    edge = Array(nodeCnt + 1) { ArrayList() }
    visited = BooleanArray(nodeCnt + 1)

    repeat(edgeCnt + 1) {
        var (start, end, isAsc) = readLine().split(" ").map { it.toInt() }
        isAsc = if(isAsc == 1) 0
        else 1
        edge[start].add(Pair(end, isAsc))
        edge[end].add(Pair(start, isAsc))
    }
    val maxTired = maxTired()
    repeat(nodeCnt + 1) { i -> visited[i] = false }
    val minTired = minTired()

    println(maxTired - minTired)
}

fun maxTired(): Int {
    var tired = 0
    val pq = PriorityQueue<Des>()
    pq.add(Des(0, 0))

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        if(visited[cur.node]) continue

        visited[cur.node] = true
        tired += cur.tired

        for(i in 0 until edge[cur.node].size) {
            if(!visited[edge[cur.node][i].first]) {
                pq.add(Des(edge[cur.node][i].first, edge[cur.node][i].second))
            }
        }
    }

    return tired * tired
}

private fun minTired(): Int {
    var tired = 0
    val pq = PriorityQueue<Asc>()
    pq.add(Asc(0, 0))

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        if(visited[cur.node]) continue

        visited[cur.node] = true
        tired += cur.tired

        for(i in 0 until edge[cur.node].size) {
            if(!visited[edge[cur.node][i].first]) {
                pq.add(Asc(edge[cur.node][i].first, edge[cur.node][i].second))
            }
        }
    }

    return tired * tired
}