[백준/BOJ] 3055번: 탈출

문제

https://www.acmicpc.net/problem/3055

3055번: 탈출

해설

각 맵에 입력되는 정보 당 상태를 보자.

• D: 비버 굴
• .: 빈 공간
• *: 물
• S: 고슴도치 
• X: 돌

고슴도치는 비버 굴로 이동해야 하며 물 또는 돌이 있는 공간은 지나갈 수 없다.

또한 물은 1분마다 인접한 칸으로 번져나간다.

즉, BFS를 두번 실행시켜야 한다는 것이다.

 

우선 각 빈 공간에 물이 몇 분이 지났을 때 차는지를 구하는 BFS를 수행한다.

이 과정이 끝났다면, 몇 분 후에 칸에 물이 차는지를 알 수 있게 된다.

 

이제 고슴도치를 움직여보자.

BFS를 수행하며 상하좌우로 움직이는데, 칸이 돌이거나, 움직인 시간이 이미 물이 차있다면 움직일 수 없다.

즉, 다음의 조건이 BFS에 추가되야 하는 것이다.

if(overflowingTime[nextY][nextX] == 0 || overflowingTime[nextY][nextX] > visited[curY][curX] + 1)

물이 처음 차있던 칸은 0이므로, 물이 차있는 칸이 0일 때도 고려를 해줘야한다. 이 조건을 추가하면 나머지는 일반 BFS랑 다를 것이 없다.

코드

import java.util.*

private lateinit var map: Array<CharArray>
private lateinit var visited: Array<IntArray>
private lateinit var overflowingTime: Array<IntArray>
private val hedgehog: Queue<Pair<Int, Int>> = LinkedList()
private val water: Queue<Pair<Int, Int>> = LinkedList()
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)

fun main() = with(System.`in`.bufferedReader()) {
    val (row, col) = readLine().split(" ").map { it.toInt() }

    map = Array(row) { CharArray(col) }
    visited = Array(row) { IntArray(col) }
    overflowingTime = Array(row) { IntArray(col) }

    repeat(row) { i ->
        val stat = readLine().toCharArray()
        repeat(col) { j ->
            map[i][j] = stat[j]
            if(map[i][j] == 'S') hedgehog.add(Pair(i, j))
            if(map[i][j] == '*')  water.add(Pair(i, j))
        }
    }

    waterFill(row, col)

    val time = move(row, col)
    if(time == 0) println("KAKTUS")
    else println(time)
}

private fun move(row: Int, col: Int): Int {
    while(hedgehog.isNotEmpty()) {
        val cur = hedgehog.poll()
        val curY = cur.first
        val curX = cur.second

        if(map[curY][curX] == 'D') return visited[curY][curX]

        for(i in 0 until 4) {
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(!inRange(nextY, nextX, row, col)) continue
            if(visited[nextY][nextX] == 0 && (map[nextY][nextX] == '.' || map[nextY][nextX] == 'D')) {
                if(overflowingTime[nextY][nextX] == 0 || overflowingTime[nextY][nextX] > visited[curY][curX] + 1) {
                    visited[nextY][nextX] = visited[curY][curX] + 1
                    hedgehog.add(Pair(nextY, nextX))
                }
            }
        }
    }

    return 0
}

private fun waterFill(row: Int, col: Int) {
    while(water.isNotEmpty()) {
        val cur = water.poll()
        val curY = cur.first
        val curX = cur.second

        for(i in 0 until 4) {
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(!inRange(nextY, nextX, row, col)) continue
            if(overflowingTime[nextY][nextX] == 0 && map[nextY][nextX] == '.') {
                overflowingTime[nextY][nextX] = overflowingTime[curY][curX] + 1
                water.add(Pair(nextY, nextX))
            }
        }
    }
}

private fun inRange(y: Int, x: Int, row: Int, col: Int): Boolean = (y in 0 until row && x in 0 until col)