[백준] 3055번: 탈출 - Kotlin[코틀린]

문제

 

3055번: 탈출

 

---

풀이

 

 고슴도치가 비버의 굴로 이동하는 가장 빠른 시간을 찾는 문제로 BFS로 해결할 수 있다. 탐색에서 물이 차는 것도 고려해야하기 때문에 Queue를 물과 고슴도치 두 개를 이용하여 해결한다.

 

 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없기때문에 한 싸이클을 물의 이동 -> 고슴도치의 이동의 순서로 구성하고 탐색을 수행한다. 물이나 고슴도치의 이동은 해당하는 현재 큐의 크기만큼 수행하고 빈공간을 만났을 때 이동한다. 고슴도치는 도착한 시간을 저장해주고 도착 지점에 도달하면 최단 시간을 갱신해준다.

 

---

코드

 

import java.util.*

data class Point(val x: Int, val y: Int, val time: Int)

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)

    val (rows, cols) = br.readLine().split(' ').map { it.toInt() }
    val map = Array(rows){ br.readLine().toString().toCharArray() }
    var ans = Int.MAX_VALUE
    val queue : Queue<Point> = LinkedList()
    val water : Queue<Point> = LinkedList()

    fun bfs() {
        while (queue.isNotEmpty()) {
            repeat(water.size) {
                val tmp = water.poll()
                for(d in 0 until 4) {
                    val nx = tmp.x + dx[d]
                    val ny = tmp.y + dy[d]

                    if(nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue
                    if(map[nx][ny] == '.') {
                        map[nx][ny] = '*'
                        water.offer(Point(nx, ny, 0))
                    }
                }
            }
            repeat(queue.size) {
                val tmp = queue.poll()
                for(d in 0 until 4) {
                    val nx = tmp.x + dx[d]
                    val ny = tmp.y + dy[d]
                    val time = tmp.time + 1

                    if(nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue

                    if(map[nx][ny] == 'D') {
                        ans = minOf(ans, time)
                        return
                    }
                    if(map[nx][ny] == '.') {
                        map[nx][ny] = 'S'
                        queue.offer(Point(nx, ny, time))
                    }
                }
            }
        }
    }

    for(i in 0 until rows) {
        for(j in 0 until cols) {
            if(map[i][j] == 'S') {
                queue.offer(Point(i, j, 0))
            } else if(map[i][j] == '*') {
                water.offer(Point(i, j, 0))
            }
        }
    }

    bfs()

    bw.write(if(ans == Int.MAX_VALUE) "KAKTUS" else "$ans")
    bw.flush()
    bw.close()
    br.close()
}