[백준/코틀린] 14938번: 서강그라운드

링크

14938번: 서강그라운드

풀이

어떤 지역에서 출발하느냐에 따라 수색 범위 m 이내에 도달할 수 있는 지역이 달라지므로,
모든 지역 쌍 간의 최단 거리를 먼저 구해야 합니다.
길은 양방향이므로 간선을 입력받을 때 양쪽 모두 저장합니다.

n이 최대 100이므로 다익스트라를 n번 돌리는 대신,
구현이 간단한 플로이드-워셜 알고리즘으로 O(n³)에 모든 쌍 최단 거리를 구할 수 있습니다.
중간 지역 k를 경유하는 경로 graph[i][k] + graph[k][j]가 기존 경로 graph[i][j]보다 짧으면 갱신합니다.

최단 거리를 모두 구한 뒤, 각 지역 i를 시작점으로 잡고
graph[i][j] <= m인 모든 지역 j의 아이템 수를 합산합니다.
이 합산 값의 최댓값이 답입니다.

코드

const val INF = Int.MAX_VALUE / 2

fun main() {
    val (n, m, r) = readln().split(" ").map { it.toInt() }
    val items = readln().split(" ").map { it.toInt() }
    val graph = List(n) { i -> MutableList(n) { j -> if (i == j) 0 else INF } }
    repeat(r) {
        val (u, v, w) = readln().split(" ").map { it.toInt() }

        graph[u - 1][v - 1] = minOf(graph[u - 1][v - 1], w)
        graph[v - 1][u - 1] = minOf(graph[v - 1][u - 1], w)
    }

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                graph[i][j] = minOf(graph[i][j], graph[i][k] + graph[k][j])
            }
        }
    }

    graph.maxOf { row ->
        row.withIndex().filter { it.value <= m }.sumOf { items[it.index] }
    }.also { println(it) }
}

연관 문제

• [백준/코틀린] 1389번: 케빈 베이컨의 6단계 법칙
• [백준/코틀린] 11403번: 경로 찾기
• [백준/코틀린] 11404번: 플로이드