2636번: 치즈 - Kotlin (BFS)

2636번: 치즈

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

 

<그림 1> 원래 치즈 모양

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

 

<그림 2> 한 시간 후의 치즈 모양

 

<그림 3> 두 시간 후의 치즈 모양

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

 

나의 풀이

이 문제는 문제에서 주어진 대로 차례차례진행하면 해결할 수 있는 문제이다. 다만 안쪽의 공기를 구하려고 생각했다면 문제 해결을 구하기는 매우 어렵다. 이 문제는 다음의 순서로 해결하는 문제이다.

 

1. 바깥공기를 bfs를 돌려서 전부 구함
2. 현재 치즈의 숫자를 구함
3. 치즈와 바깥공기가 접촉한 칸의 치즈는 기록해뒀다가 한번에 녹임
4. 현재 치즈의 숫자가 0이라면 시간과 이전 단계의 치즈의 숫자를 출력

 

나는 바깥의 공기를 9로 정하고 문제를 해결하였다.

 

import java.util.*

val dx = arrayOf(0, 1, 0, -1)
val dy = arrayOf(1, 0, -1, 0)

lateinit var board: Array<IntArray>

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    board = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }

    var lastCheese = 0
    var time = 0
    while (true) {
        // 바깥공기를 전부 9로 바꿈
        findOutsideAir(n, m)

        // 치즈의 개수를 새면서 해당하는 위치에 9가 접하는지 판단
        var cheese = 0
        val cheeseList = mutableListOf<Pair<Int, Int>>()
        for (i in 0 until n) {
            for (j in 0 until m) {
                if (board[i][j] == 1) {
                    cheese++
                    if(check(n, m, i, j))
                        cheeseList.add(i to j)
                }
            }
        }

        // 치즈의 개수가 0이라면 탈출하고 0이 아니라면 치즈의 개수 기록
        if (cheese == 0) break
        else lastCheese = cheese

        // 9가 접하는 치즈들을 9로 전부 다 바꿈
        cheeseList.map{
            board[it.first][it.second] = 9
        }

        time++
    }

    println(time)
    println(lastCheese)
}

fun findOutsideAir(n: Int, m: Int) {
    val queue : Queue<Pair<Int, Int>> = LinkedList()
    val visited = Array(n) { BooleanArray(m) }

    queue.add(0 to 0)
    visited[0][0] = true
    board[0][0] = 9

    while (queue.isNotEmpty()) {
        val (x, y) = queue.poll()

        for (i in 0 until 4) {
            val tempX = x + dx[i]
            val tempY = y + dy[i]

            if (tempX in 0 until n &&
                tempY in 0 until m &&
                !visited[tempX][tempY]) {
                if (board[tempX][tempY] == 0 || board[tempX][tempY] == 9) {
                    visited[tempX][tempY] = true
                    board[tempX][tempY] = 9
                    queue.add(tempX to tempY)
                }
            }

        }
    }
}

fun check(n: Int, m: Int, cheeseX: Int, cheeseY: Int): Boolean {
    for (i in 0 until 4) {
        val tempX = cheeseX + dx[i]
        val tempY = cheeseY + dy[i]

        if (tempX in 0 until n &&
            tempY in 0 until m &&
            board[tempX][tempY] == 9) return true
    }
    return false
}