[백준 14938번][Kotlin] 서강그라운드

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

14938번: 서강그라운드

 

난이도 : 골드 4
태그 : 그래프 이론, 데이크스트라, 플로이드-워셜

 

 

설명

각 정점에서 m 만큼의 비용 안에 갈 수 있는 정점들의 아이템 값의 최대값을 구하는 문제입니다.

 

한 정점과 연결된 다른 정점을 순차적으로 탐색하는 방식으로

DFS, 다익스트라 알고리즘을 사용해 풀이할 수도 있지만,

 

본 포스팅에서는 플로이드 - 워셜 알고리즘을 사용하여 풀이하겠습니다.

 

 

소스코드

인풋값 세팅

val MAX_VALUE = 10000000

val br = BufferedReader(InputStreamReader(System.`in`))

val nmr = br.readLine().split(" ").map { it.toInt() }
val n = nmr[0] // 지역 개수
val m = nmr[1] // 수색 범위
val r = nmr[2] // 길의 개수

val items = Array(n + 1) { 0 }
val weight = Array(n + 1) { Array(n + 1) { MAX_VALUE } }

val st = StringTokenizer(br.readLine(), " ")

repeat(n) { items[it + 1] = st.nextToken().toInt() }
repeat(n) { weight[it + 1][it + 1] = 0 }

for (i in 1..r) {
    val st2 = StringTokenizer(br.readLine(), " ")
    val v1 = st2.nextToken().toInt()
    val v2 = st2.nextToken().toInt()
    val w = st2.nextToken().toInt()
    weight[v1][v2] = w
    weight[v2][v1] = w
}

 

items는 각 정점들이 가지고 있는 아이템의 값을 의미합니다.

weight는 한 정점에서 다른 정점으로 가는 가중치를 담은 배열입니다.

 

초기값은 갈 수 있는 길이 없다는 의미로 MAX_VALUE로 초기화를 해주었고,

본 문제에서 간선은 양방향이므로 weight[v1][v2]와 weight[v2][v1]을 같은 값으로 저장합니다.

 

또, 자기 자신으로 향하는 비용은 0이므로 weight[1][1], weight[2][2], weight[3][3] 등

자기 자신으로 가는 간선의 비용은 0으로 할당합니다.

 

 

플로이드 - 워셜

for (k in 1..n) {
    for (i in 1..n) {
        for (j in 1..n) {
            if (weight[i][k] + weight[k][j] < weight[i][j]) {
                weight[i][j] = weight[i][k] + weight[k][j]
            }
        }
    }
}

플로이드 - 워셜 알고리즘을 적용합니다.

 

 

 

해당 알고리즘을 설명하면 다음과 같습니다.

 

a 정점에서 c 정점으로 가는 비용이 10이 듭니다.

a 정점에서 b 로 가는 비용이 3이며, b 정점에서 c 정점으로 가는 비용이 5일때,

a 정점에서 c로 가는 비용(10) 보다 a 정점에서 b를 거쳐 c로 가는 비용(3+5=8)이 더 낮은 코스트를 보입니다.

 

위 코드상에선 i를 시작점, j를 도착점, k를 경유점으로 보고

 

weight[i][j] (i에서 j로 가는 비용)과 weight[i][k] + weight[k][j] (i에서 k를 거쳐 j로 가는 비용)을 비교하여,

더 저렴한 비용으로 테이블을 갱신하면 됩니다.

 

 

 

 

최대 아이템 개수

var max = 0

for (i in 1..n) {
    var sum = 0

    for (j in 1..n) {
        if (weight[i][j] <= m) {
            sum += items[j]
        }
    }

    if (max < sum) max = sum
}

println(max)

 

 

 

각 정점에서 다른 정점까지, 거리가 m 이내인 모든 정점의 아이템 값을 총합하고,

이전 정점의 아이템 합보다 크다면 max를 갱신합니다.

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main() {
    val MAX_VALUE = 10000000

    val br = BufferedReader(InputStreamReader(System.`in`))

    val nmr = br.readLine().split(" ").map { it.toInt() }
    val n = nmr[0] // 지역 개수
    val m = nmr[1] // 수색 범위
    val r = nmr[2] // 길의 개수

    val items = Array(n + 1) { 0 }
    val weight = Array(n + 1) { Array(n + 1) { MAX_VALUE } }

    val st = StringTokenizer(br.readLine(), " ")

    repeat(n) { items[it + 1] = st.nextToken().toInt() }
    repeat(n) { weight[it + 1][it + 1] = 0 }

    for (i in 1..r) {
        val st2 = StringTokenizer(br.readLine(), " ")
        val v1 = st2.nextToken().toInt()
        val v2 = st2.nextToken().toInt()
        val w = st2.nextToken().toInt()
        weight[v1][v2] = w
        weight[v2][v1] = w
    }

    for (k in 1..n) {
        for (i in 1..n) {
            for (j in 1..n) {
                if (weight[i][k] + weight[k][j] < weight[i][j]) {
                    weight[i][j] = weight[i][k] + weight[k][j]
                }
            }
        }
    }

    var max = 0

    for (i in 1..n) {
        var sum = 0

        for (j in 1..n) {
            if (weight[i][j] <= m) {
                sum += items[j]
            }
        }

        if (max < sum) max = sum
    }

    println(max)
}

 

 

후기

 

처음엔 다익스트라로 접근을 했다가,

한 정점에서 다른 정점까지 거리를 하나하나 계산해야 하니,

플로이드 - 워셜로 접근하는 것이 낫겠다 생각해 풀이한 문제입니다.

 

같은 최단경로 알고리즘중 하나인 다익스트라는

한 정점에서 다른 정점까지의 최단경로를 계산하는 반면,

플로이드 워셜 알고리즘은 모든 노드쌍에 대해 최단경로를 구하는 것이 차이점입니다.

 

 

 

부디 스타팅 포인트를 잘 선정해서 치킨을 먹었으면 좋겠네요.