[백준] 4485번: 녹색 옷 입은 애가 젤다지? - Kotlin[코틀린]

문제

 

4485번: 녹색 옷 입은 애가 젤다지?

 

---

풀이

 

 다익스트라 알고리즘을 사용하여 최단 거리를 찾을 수 있다. 알고리즘은 우선 순위 큐를 활용하여 현재까지 발견된 최단 거리를 가진 정점을 기준으로 탐색한다. 각 정점까지의 사용되는 비용을 저장하는 배열을 만들고 시작 지점의 비용을 초기화해준다. 그 후, 우선 순위 큐에 시작 지점을 추가하고 탐색을 시작한다.

 탐색 중에는 현재까지 저장된 비용보다 더 작은 비용으로 이동할 수 있는 경우에 해당 정점의 비용을 갱신하고 큐에 추가한다. 이 과정을 반복하면서 모든 정점에 대한 최단 거리를 계산할 수 있다.

 

 문제에서 구하는 시작 지점에서 목적지까지의 최소 비용을 출력하면 된다.

 

---

코드

 

import java.util.*

data class Point(val x: Int, val y: Int, val value: Int) : Comparable<Point> {
    override fun compareTo(other: Point): Int = value - other.value
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    // 상, 하, 좌, 우 이동을 위한 배열
    val dx = arrayOf(1, 0, -1, 0)
    val dy = arrayOf(0, 1, 0, -1)

    var num = 0
    lateinit var map: Array<IntArray> // 입력받을 지도

    // 다익스트라 알고리즘을 이용한 최단 거리 계산 함수
    fun dijkstra(): Int {
        val cost = Array(num) { IntArray(num) { Int.MAX_VALUE } }
        val queue = PriorityQueue<Point>()

        // 시작 지점 초기화
        cost[0][0] = map[0][0]
        queue.offer(Point(0, 0, map[0][0]))

        while (queue.isNotEmpty()) {
            val cur = queue.poll()

            // 인접한 정점들에 대한 탐색
            for (i in 0 until 4) {
                val nx = cur.x + dx[i]
                val ny = cur.y + dy[i]

                if (nx < 0 || ny < 0 || nx >= num || ny >= num) continue

                // 더 작은 비용으로 갱신 가능한 경우
                if (cost[nx][ny] > cost[cur.x][cur.y] + map[nx][ny]) {
                    cost[nx][ny] = cost[cur.x][cur.y] + map[nx][ny]
                    queue.offer(Point(nx, ny, cost[nx][ny]))
                }
            }
        }

        // 목적지까지의 최단 거리 반환
        return cost[num - 1][num - 1]
    }

    val sb = StringBuilder()
    var time = 1
    while (true) {
        num = br.readLine().toInt()
        if (num == 0) break
        map = Array(num) { IntArray(num) }
        for (i in 0 until num) {
            val st = StringTokenizer(br.readLine())
            for (j in 0 until num) {
                map[i][j] = st.nextToken().toInt()
            }
        }

        sb.append("Problem $time: ${dijkstra()}\n")
        time++
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}