[백준/BOJ] 2636번: 치즈

문제

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

2636번: 치즈

해설

판의 가장자리에는 치즈가 놓여있지 않다고 문제에 나와있다.

즉, (0, 0)의 위치 또는 각 판의 가장자리 어디서든 bfs 혹은 dfs를 이용하여 탐색을 해나가면 안에 공기에 접해있는 치즈만을 녹일 수 있다.

치즈가 전부 녹을 때까지 bfs를 수행해줘야 한다. 따라서 bfs를 한 번만 수행하는 것이 아닌, 모든 치즈가 사라질 때까지 반복을 해야 한다.

이를 알기 위해 bfs를 수행하는 과정에서 1(치즈)이 있다면 치즈의 개수를 저장한 변수(cnt라고 하자)를 ++해준다.

만약 bfs가 마치고 cnt가 0이 아니라면 bfs를 또 수행해야 한다는 것이고, 그다음에 모든 치즈가 녹을 수 있으므로 치즈의 개수를 저장시켜준다. cnt가 0이라면 모든 치즈가 녹은 것이므로 그전에 저장한 치즈의 개수와 시간을 출력해주면 된다.

코드

import java.util.*

private lateinit var map: Array<IntArray>
private lateinit var visited: Array<BooleanArray>
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var ans = 0
private var time = 0

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

    map = Array(row) { IntArray(col) }
    visited = Array(row) { BooleanArray(col) }

    repeat(row) { i ->
        val st = StringTokenizer(readLine())
        repeat(col) { j ->
            map[i][j] = st.nextToken().toInt()
        }
    }

    while(true) {
        if(melt(row, col)) break

        for(i in 0 until row) visited[i].fill(false)
    }
}

private fun melt(row: Int, col: Int): Boolean {
    var cnt = 0
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(0, 0))
    visited[0][0] = true
    time++

    while(que.isNotEmpty()) {
        val cur = que.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(isCondition(nextY, nextX, row, col)) {
                if(map[nextY][nextX] == 0) {
                    que.add(Pair(nextY, nextX))
                }
                else {
                    map[nextY][nextX] = 0
                    cnt++
                }

                visited[nextY][nextX] = true
            }
        }
    }

    return if(cnt == 0) {
        println(--time)
        println(ans)
        true
    }
    else {
        ans = cnt
        false
    }
}

private fun isCondition(y: Int, x: Int, row: Int, col: Int) = (y in 0 until row && x in 0 until col && !visited[y][x])