[백준/BOJ] 14938번: 서강그라운드

문제

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

14938번: 서강그라운드

해설

어떠한 지역에 떨어졌을 때, 수색 범위 안에서 가장 많은 아이템을 얻을 수 있는지를 구하는 문제이다.

우선 모든 지역에서의 범위를 구해야 하기 때문에

1번 지역에 떨어졌을 때 모든 지역까지의 거리를 구해야 하고,

2번 지역에 떨여졌을 때 모든 지역까지의 거리, 3번, 4번 . . .  n번에 떨어졌을 때의 모든 지역까지의 거리를 구해야 한다.

 

모든 지역까지의 거리를 구하는 알고리즘으로 다익스트라 알고리즘을 사용하였다. 

어떠한 지점에 떨어졌을 때 그 지점으로부터 모든 지역까지의 거리를 구한 후, 수색 범위 안에 있는 지역들의 아이템 개수를 모두 더해주면 된다.

 

이 과정을 반복문을 통해 모든 지역에 떨어졌을 때 얻을 수 있는 아이템 갯수를 구해준 후, 가장 많이 얻을 수 있는 아이템 갯수를 출력시켜주면 되는 문제이다.

코드

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

data class Position(val areaNum: Int, val distance: Int): Comparable<Position> {
    override fun compareTo(other: Position): Int = distance - other.distance
}

private lateinit var map: Array<ArrayList<Position>>
private lateinit var itemCnt: IntArray
private lateinit var betweenDistance: IntArray

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

    map = Array(areaCnt + 1) { ArrayList(areaCnt + 1) }
    itemCnt = IntArray(areaCnt + 1)
    betweenDistance = IntArray(areaCnt + 1)

    val st = StringTokenizer(readLine())
    for(i in 1 .. areaCnt) itemCnt[i] = st.nextToken().toInt()

    repeat(roadCnt) {
        val (from, to, distance) = readLine().split(" ").map { it.toInt() }
        map[from].add(Position(to, distance))
        map[to].add(Position(from, distance))
    }

    var ans = 0
    for(i in 1 .. areaCnt) {
        ans = max(dijkstra(i, areaCnt, searchRange), ans)
    }

    println(ans)
}

private fun dijkstra(start: Int, areaCnt: Int, searchRange: Int): Int {
    betweenDistance.fill(Integer.MAX_VALUE)

    val pq = PriorityQueue<Position>()
    pq.add(Position(start, 0))
    betweenDistance[start] = 0

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val curArea = cur.areaNum
        val curDistance = cur.distance

        for(i in map[curArea]) {
            if(betweenDistance[i.areaNum] > curDistance + i.distance) {
                betweenDistance[i.areaNum] = curDistance + i.distance
                pq.add(Position(i.areaNum, betweenDistance[i.areaNum]))
            }
        }
    }

    var total = 0
    for(i in 1 .. areaCnt) {
        if(betweenDistance[i] <= searchRange) {
            total += itemCnt[i]
        }
    }

    return total
}