[백준/BOJ] 2638번: 치즈

문제

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

2638번: 치즈

해설

문제에서는 치즈의 외부 공기와 내부 공기로 나뉘어 있다.

외부 공기에 2면 이상이 닿아있다면, 그 부분은 녹는다. 내부 공기에 닿은 것은 무시하여도 된다는 것이다.

따라서 문제를 크게 나눠보면 다음과 같다.

1. 외부 공기와 내부 공기를 구분한다.
2. 현재 위치에 있는 치즈가 두 면 이상이 닿았는지 확인하고, 2면 이상 닿아있다면 그 치즈를 녹인다.
3. 더 녹일 치즈가 있는지 확인한다.

이 문제에서는 위의 단계를 3번에서 더 녹일 치즈가 없을 때까지 반복해야 하므로 bfs를 여러 번 돌려야 한다.

따라서 무한 반복을 실행시키고, 모든 조건이 만족됬을 때 반복문을 탈출하면 된다.

 

우선, 외부 공기와 내부 공기를 구분해주자.

이 과정에서 bfs를 통해 외부의 공기라면 -1로 처리해준다.

 

1번 과정이 끝났다면 가로(1 ~ n - 1), 세로(1 ~ m-1)를 확인해주자. 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다는 가정이 문제에 있기 때문에 1 ~ n-1, m-1만을 확인하면 된다.

이중 반복문을 통해 모눈종이를 탐색하다가, 현재 위치가 치즈라면 4면을 확인해준다.

확인 후 2면 이상이 외부 공기에 닿아있다면, 현재 위치의 치즈를 녹인 후, 녹은 치즈의 개수를 증가시킨다.

 

모눈종이의 탐색이 끝났다면, 녹은 치즈의 개수를 확인해본다.

이때 녹은 치즈의 개수가 0이라면, 모든 치즈가 다 녹은 것이므로 반복문을 나와 걸린 시간을 출력해준다.

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 row = 0
private var col = 0

fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    row = st.nextToken().toInt()
    col = st.nextToken().toInt()

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

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

    var time = 0
    while(true) {
        var meltCheeze = 0
        visited = Array(row) { BooleanArray(col) }

        setExternalAir()

        for(i in 1 until row - 1) {
            for(j in 1 until col - 1) {
                if(map[i][j] == 1) {
                    if(isMelt(i, j)) {
                        map[i][j] = 0
                        meltCheeze++
                    }
                }
            }
        }

        if(meltCheeze == 0) break
        time++
    }

    println(time)
}

private fun setExternalAir() {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(0, 0))
    map[0][0] = -1

    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(!inRange(nextY, nextX)) continue
            if(map[nextY][nextX] == 1 || visited[nextY][nextX]) continue

            map[nextY][nextX] = -1
            visited[nextY][nextX] = true
            que.add(Pair(nextY, nextX))
        }
    }
}

private fun isMelt(y: Int, x: Int): Boolean {
    var cnt = 0

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

        if(!inRange(nextY, nextX)) continue
        if(map[nextY][nextX] == -1) cnt++
    }

    return cnt >= 2
}

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