[백준] 알고스팟 (1261)(Kotlin)

원본 문제 : https://www.acmicpc.net/problem/1261

문제 참고. : https://stack07142.tistory.com/131

 

<첫번째> 다익스트라(adjacency list)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

val dRow: IntArray = intArrayOf(-1,1,0,0)
val dCol: IntArray = intArrayOf(0,0,-1,1)

var ROW: Int = 0
var COL: Int = 0

var map: Array<IntArray> = arrayOf()
var distance: Array<IntArray> = arrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val nm = readLine().split(" ")
    ROW = nm[0].toInt()
    COL = nm[1].toInt()

    map = Array( COL+1 ) { IntArray( ROW+1 ) }
    distance = Array ( COL+1 ) { IntArray( ROW+1 ) }

    for ( i in 1 until COL+1 ) {
        Arrays.fill(distance[i], 1000000)
    }

    for ( i in 1 until COL+1 ) {
        val str = readLine().toCharArray()
        for ( j in 1 until ROW+1 ) {
            map[i][j] = str[j-1] - '0'
        }
    }

    dijkstra()
}

fun dijkstra() {

    val pq: PriorityQueue<Node> = PriorityQueue<Node>()

    pq.add( Node(1, 1, 0 ) )
    distance[1][1] = 0

    while ( !pq.isEmpty() ) {

        val now = pq.poll()

        if ( now.row == ROW && now.col == COL ) {
            println(now.cost)
            break
        }

//        if (distance[now.col][now.row] < now.cost) continue

        for ( i in 0 until 4 ) {
            val nextR = now.row + dRow[i]
            val nextC = now.col + dCol[i]

            if ( nextR <= 0 || nextC <= 0 || nextR > ROW || nextC > COL ) continue

            if ( distance[nextC][nextR] > distance[now.col][now.row] + map[nextC][nextR]) {
                distance[nextC][nextR] = distance[now.col][now.row] + map[nextC][nextR]
                pq.add( Node(nextR, nextC, distance[nextC][nextR]) )
            }
        }
    }
}

class Node : Comparable<Node> {

    var row: Int = 0
    var col: Int = 0
    var cost: Int = 0

    constructor(row: Int, col: Int, cost: Int) {
        this.row = row
        this.col = col
        this.cost = cost
    }

    override fun compareTo(other: Node): Int {
        return this.cost - other.cost
    }
}