백준 - 녹색 옷 입은 애가 젤다지?(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/4485

 

[문제 설명]

-가 최소한으로 되게 최종 도착지까지 가세요.

 

[접근 방법]

일단, 도착지까지 간다는 점에서 최단거리 알고리즘이 떠오를 것이다.

그런데. 이 문제에서는 비용이 음수로 주어진다.

다익스트라 알고리즘의 경우 간선에 음수 가중치가 있으면 사용하지 못하므로, 벨만포드 알고리즘을 구현이 필요하다고 생각할 수도 있다.

그러나, 문제의 조건으로 모든 간선이 음수 가중치라는 조건을 줬다. 이러면 양수나 음수나 사실상 의미가 없다.

결국, 절댓값이 최솟값인 최단거리 알고리즘이므로 다익스트라로 간단히 구현 가능하다.

그리고 저번에도 말했지만, 다익스트라는 dp 배열에 초기값 설정이 중요하다.

모든 맵을 최댓값으로 돈다고 가정했을 때 125 * 125 * 9이므로 이보다 1이 더 큰 값을 초기값으로 잡아줬다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.PriorityQueue

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var noOfProblem = 1
    while (true) {
        val n = br.readLine().toInt()
        if (n == 0) {
            break
        }

        val map = Array(n) { br.readLine().split(" ").map { it.toInt() }.toIntArray() }
        bw.write("Problem $noOfProblem: ${getMinEscapeCost(startPoint = Position(0, 0, map[0][0]), map = map)}\n")
        noOfProblem++
    }
    bw.flush()
}

class Position(val r: Int, val c: Int, val cost: Int)
val dy = intArrayOf(-1, 0, 1, 0)
val dx = intArrayOf(0, 1, 0, -1)
fun getMinEscapeCost(startPoint: Position, endPointR: Int = 0, endPointC: Int = 0, map: Array<IntArray>): Int {
    val visited = Array(map.size) { BooleanArray(map.size) }
    val dp = Array(map.size) { IntArray(map.size) { 1406251 } }
    dp[0][0] = startPoint.cost
    val pq = PriorityQueue<Position>(compareBy { position -> position.cost })
    pq.offer(startPoint)

    while (pq.isNotEmpty()) {
        val cPosition = pq.poll()

        if (visited[cPosition.r][cPosition.c]) {
            continue
        }
        visited[cPosition.r][cPosition.c] = true

        for (dIdx in 0..3) {
            val nextY = cPosition.r + dy[dIdx]
            val nextX = cPosition.c + dx[dIdx]

            if (nextY !in map.indices || nextX !in map.indices) {
                continue
            }

            if (dp[cPosition.r][cPosition.c] + map[nextY][nextX] < dp[nextY][nextX]) {
                dp[nextY][nextX] = dp[cPosition.r][cPosition.c] + map[nextY][nextX]
                pq.offer(Position(nextY, nextX, dp[cPosition.r][cPosition.c] + map[nextY][nextX]))
            }
        }
    }

    return dp[map.size - 1][map.size - 1]
}