[백준] 상범 빌딩 (6593)(Kotlin)

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

문제 참고(두번째) : https://suriisurii.tistory.com/7

 

<첫번째> 실패(메모리 초과)

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

var L: Int = 0
var R: Int = 0
var C: Int = 0

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

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

    var lrc = readLine().split(" ")

    L = lrc[0].toInt()
    C = lrc[1].toInt()
    R = lrc[2].toInt()

    while ( L != 0 ) {

        map = Array( L + 1 ) {
            Array( C + 1) {
                IntArray( R + 1 )
            }
        }

        distance = Array( L + 1 ) {
            Array(C + 1) {
                IntArray(R + 1)
            }
        }

        var start: Boolean = false
        var end: Boolean = false

        var startArray: IntArray = IntArray( 3 )
        var endArray: IntArray = IntArray( 3 )

        for ( i in 0 until L+1 ) {
            for ( j in 0 until C+1 ) {
                Arrays.fill(distance[i][j], 100000)
            }
        }

        for ( i in 1 until L+1 ) {
            for ( j in 1 until C+1 ) {
                var str = readLine().toCharArray()

                if ( str.isEmpty() ) str = readLine().toCharArray()

                for ( k in 1 until R+1 ) {

                    val char: Char = str[k-1]

                    if ( start == false || end == false ) {
                        if ( char == 'S' ) {
                            startArray[0] = i
                            startArray[1] = j
                            startArray[2] = k
                        }
                        else if ( char == 'E') {
                            endArray[0] = i
                            endArray[1] = j
                            endArray[2] = k
                        }
                    }

                    if ( str[k-1] != '#') {
                        map[i][j][k] = 0
                    }
                    else {
                        map[i][j][k] = 100000
                    }
                }
            }
        }


        dijkstra(startArray, endArray)

        Arrays.fill(startArray, 0)
        Arrays.fill(endArray, 0)

        lrc = readLine().split(" ")
        if ( lrc[0] == "" ) lrc = readLine().split(" ")

        L = lrc[0].toInt()
        C = lrc[1].toInt()
        R = lrc[2].toInt()

    }


}

fun dijkstra(start: IntArray, end: IntArray) {

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

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

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

    while ( !pq.isEmpty() ) {

        val now = pq.poll()

        if ( now.level == end[0] && now.col == end[1] && now.row == end[2] ) break

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

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

            if ( nextC <= 0 || nextR <= 0 || nextC > C || nextR > R ) continue

            if ( map[now.level][nextC][nextR] >= 100000 ) continue

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

                for ( i in 0 until 2 ) {
                    val nextL = dLev[i] + now.level

                    if ( nextL <= 0 || nextL > L ) continue

                    if ( map[nextL][nextC][nextR] >= 100000 ) continue

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

            }
        }
    }

    if ( distance[end[0]][end[1]][end[2]] == 100000 ) {
        println("Trapped!")
    }

    else {
        println("Escaped in ${distance[end[0]][end[1]][end[2]]} minutes(s)")
    }

}

class Node : Comparable<Node> {

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

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

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

 

<두번째>

import java.util.*

var L: Int = 0
var R: Int = 0
var C: Int = 0

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

var start: Point? = null
var end: Point? = null

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

fun main() {
    val sc: Scanner = Scanner(System.`in`)

    while (true) {

        L = sc.nextInt()
        C = sc.nextInt()
        R = sc.nextInt()

        if (L == 0 && R == 0 && C == 0) break

        map = Array(L+1) {
            Array(C+1) {
                CharArray(R+1)
            }
        }

        distance = Array(L+1) {
            Array(C+1) {
                IntArray(R+1)
            }
        }

        for (i in 1 until L+1) {
            for (j in 1 until C+1) {
                var temp = sc.next()
                for (k in 1 until R+1) {
                    map[i][j][k] = temp[k-1]
                    if (temp[k-1] == 'S'){
                        start = Point(i, j, k)
                    }
                    if (temp[k-1] == 'E') {
                        end = Point(i, j, k)
                    }
                }
            }
        }

        dijkstra()

        val answer = distance[end!!.lev][end!!.col][end!!.row]
        if (answer == 0) {
            println("Trapped!")
        }
        else {
            println("Escaped in ${answer} minute(s).")
        }

    }
}

fun dijkstra() {
    val queue: Queue<Point> = LinkedList<Point>()
    queue.add(start)

    while (!queue.isEmpty()) {
        val now = queue.poll()

        for (i in 0 until 6) {
            val nextL: Int = now.lev + dLev[i]
            val nextC: Int = now.col + dCol[i]
            val nextR: Int = now.row + dRow[i]

            if (nextL <= 0 || nextL > L || nextC <= 0 || nextC > C || nextR <= 0 || nextR > R) continue
            if (map[nextL][nextC][nextR] == '#') continue
            if (distance[nextL][nextC][nextR] != 0) continue

            distance[nextL][nextC][nextR] = distance[now.lev][now.col][now.row] + 1
            queue.add(Point(nextL, nextC, nextR))
        }
    }
}

class Point {
    var lev: Int = 0
    var col: Int = 0
    var row: Int = 0
    constructor(lev: Int, col: Int, row: Int) {
        this.lev = lev
        this.col = col
        this.row = row
    }
}