[백준] 치즈 (Kotlin)

문제 바로가기

어제 진행되었던 2023 Spring Coding - 스타트업 인턴 프로그램의 2번 문제가 해당 문제와 비슷하여, 복습할 겸 풀어보았다.

문제

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

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

<그림 1> 원래 치즈 모양

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

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

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

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

입력

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

출력

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

접근 과정 1

이 문제를 처음 보고 나서 든 생각은 치즈 외곽의 공기에서 상하좌우 BFS를 진행하면서 새로운 좌표를 만날 때마다 방문 배열에 체크를 해주고, 만약 공기를 만나면 큐에 해당 좌표를 넣고 BFS를 계속 진행하고, 만약 처음으로 치즈를 만나게 된다면 녹여주는 것을 하나의 시간 단위로 반복시켜주었다. 치즈가 다 사라질 때까지 해당 과정을 반복하다가, 다 사라지기 직전 과정의 치즈조각 갯수와 걸리는 시간(위 과정 반복 수)를 출력해주면 된다.

1번의 접근과정으로 푼 코드는 다음과 같았다.

import java.util.LinkedList
import java.util.Queue

private lateinit var map: Array<IntArray>
private lateinit var visited: Array<BooleanArray>
private lateinit var dx: IntArray
private lateinit var dy: IntArray
private var n: Int = 0
private var m: Int = 0
private var cheese: Int = 0
private var cnt: Int = 0

fun main() {
    val rc = readln().split(" ").map { it.toInt() }
    val history: ArrayList<Int> = arrayListOf()
    n = rc[0]
    m = rc[1]
    map = Array(n) { IntArray(m) }
    dx = intArrayOf(-1, 1, 0, 0)
    dy = intArrayOf(0, 0, -1, 1)

    repeat(n) { row ->
        val line = readln().split(" ").map { it.toInt() }
        repeat(m) { col ->
            map[row][col] = line[col]
            if(map[row][col] == 1) cheese++
        }
    }

    while (cheese > 0) {
        cnt++
        history.add(cheese)
        bfs(0, 0)
    }

    println(cnt)
    print(history.last())
}

private fun bfs(x: Int, y: Int) {
    val q: Queue<Pair<Int, Int>> = LinkedList()
    q.offer(Pair(x, y))
    visited = Array(n) { BooleanArray(m) }
    visited[x][y] = true

    while (q.isNotEmpty()) {
        val point = q.poll()
        for (i in 0 until 4) {
            val nx = point.first + dx[i]
            val ny = point.second + dy[i]
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue
            if (!visited[nx][ny]) {
                visited[nx][ny] = true
                if (map[nx][ny] == 0) q.offer(Pair(nx, ny))
                else {
                    cheese--
                    map[nx][ny] = 0
                }
            }
        }
    }
}

접근 과정 2

치즈 내부의 빈 칸과 치즈 외부의 빈 칸을 구분하여, 가령 치즈 외곽의 빈 칸들은 3으로 표기해두고, 치즈인 칸들을 기준으로 상하좌우 중 적어도 두 칸 이상이 외곽의 빈 칸(공기)이라면, 그 치즈 칸을 다음 과정에 녹을 대상으로 표기한다. 녹을 대상을 전부 표기했다면, 그 칸들을 전부 외곽의 빈 칸(공기)로 바꿔준다. 그 다음 외부,내부 공기를 구분 -> 치즈 녹이기 과정을 반복한다.

해당 접근방법으로 풀이한 다른 분의 글이 있으니 한 번 참고해보자.