[Kotlin] BOJ2665 미로만들기

링크 : https://www.acmicpc.net/problem/2665

2665번: 미로만들기

알고스팟 문제와 상당히 유사한 (거의 빼다박은 수준)  문제

( 알고스팟 링크 : https://www.acmicpc.net/problem/1261 )

1261번: 알고스팟

 

이 문제 또한 각 노드에 번호를 메겨서

벽이 없는 노드의 cost = 0 

벽이 있는 노드의 cost = 1 로 지정하여

다익스트라로 최단거리를 구하면 되는 문제이다.

---

소스코드(Dijkstra)

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

private val MY = arrayOf(1,-1,0,0) //상하좌우
private val MX = arrayOf(0,0,-1,1) //상하좌우

private var N = 0 //(1 ≤ N ≤ 50)
private lateinit var minCostList :MutableList<Int>
private lateinit var map : List<MutableList<Int>>
private fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    N = br.readLine().toInt()
    minCostList = MutableList(N*N){ Int.MAX_VALUE }
    minCostList[0] = 0
    //흰방 0 , 검은방 1로 재 구성
    map = List(N){br.readLine().toCharArray().map{if (it == '0') 1 else 0}.toMutableList()}
    dijkstra(Node(0,0,0))

    println(minCostList.last())
}

private fun dijkstra(start :Node){
    val PQ = PriorityQueue<Node>()
    PQ.add(start)
    while(PQ.isNotEmpty()){
        val node = PQ.poll()
        if (minCostList[node.num] < node.cost) continue
        for (i in 0 until 4){
            val nextY = node.y + MY[i]
            val nextX = node.x + MX[i]
            if (isInMap(nextY,nextX)){
                val cost = node.cost + map[nextY][nextX]
                if (cost < minCostList[getNodeNum(nextY,nextX)]){
                    PQ.add(Node(nextY,nextX,cost))
                    minCostList[getNodeNum(nextY,nextX)] = cost
                }
            }
        }
    }
}

private fun isInMap(y :Int, x :Int)
    = (y in 0 until N) && (x in 0 until N)

private fun getNodeNum(y :Int, x :Int)
    = N*y + x

data class Node(
    val y :Int,
    val x :Int,
    val cost :Int,
    val num :Int = N*y + x
): Comparable<Node> {
    override fun compareTo(other: Node): Int
        = this.cost - other.cost
}