<백준> 토마토(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%ED%86%A0%EB%A7%88%ED%86%A0(7569)

[백준]

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

제출 결과

 

뭔가 익숙하다 했더니 이전에 쉬운 버전의 토마토 문제를 풀어본 적이 있더라

그런데 이름이 똑같아서 깃허브에 저장할 때 에러나고 순간 당황했다...ㅎ

그 문제와 다른 점은 상자가 높이를 가지는 3차원이라는 것과 2차원 상의 상하좌우말고 높이의 위아래도 체크해야한다는 것이었다.

 

입력이 가장 어려울 줄 알았는데 생각보다 쉽게 접근해서 해결했다.

그래도... Array<Array<Array<Int>>>는 익숙해지지 않는다.

지연초기화하고 3중 반복문을 통해 입력값을 받았다.

익은 토마토가 있는 자리는 큐에 저장해놓고 토마토가 없는 자리는 개수를 세어놨다.

 

그리고 BFS를 돌리는데 3차원이기에 Triple을 사용했다.

흐름은 기본 흐름과 동일했고 BFS가 끝났을 때 모든 칸이 다 익었는지 확인하기 위해 3중 반복문으로 도는 함수를 추가로 만들었다.

가로, 세로, 높이가 헷갈려서 그렇지... 문제는 쉬웠다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.util.StringTokenizer

var m: Int = 0
var n: Int = 0
var h: Int = 0
var check: Int = 0

lateinit var box: Array<Array<Array<Int>>>
lateinit var visited: Array<Array<Array<Boolean>>>
val q = ArrayDeque<Triple<Int, Int, Int>>()

val dy = listOf(0, 1, 0, -1, 0, 0)
val dx = listOf(1, 0, -1, 0, 0, 0)
val dz = listOf(0, 0, 0, 0, 1, -1)
fun main() = with(System.`in`.bufferedReader()) {
    with(StringTokenizer(readln())) {
        m = this.nextToken().toInt()
        n = this.nextToken().toInt()
        h = this.nextToken().toInt()
    }

    box = Array(h) { Array(n) { Array(m) { 0 } } }
    visited = Array(h) { Array(n) { Array(m) { false } } }
    for (i in 0 until h) {
        for (j in 0 until n) {
            val st = StringTokenizer(readln())
            for (k in 0 until m) {
                box[i][j][k] = st.nextToken().toInt()
                if (box[i][j][k] == 1) {
                    q.add(Triple(i, j, k))
                    visited[i][j][k] = true
                } else if (box[i][j][k] == -1) {
                    check++
                }
            }
        }
    }

    println(bfs())
}

fun bfs(): Int {
    var count = 0

    q.add(Triple(-1, -1, -1))

    while (q.isNotEmpty()) {
        val cur = q.removeFirst()
        
        if (cur.first == -1 && q.isNotEmpty()) {
            q.add(Triple(-1, -1, -1))
            count++
        }

        for (i in 0 until 6) {
            val newHeight = cur.first + dz[i]
            val newRow = cur.second + dy[i]
            val newCol = cur.third + dx[i]


            if (newHeight < 0 || newHeight >= h || newRow < 0 || newRow >= n || newCol < 0 || newCol >= m) continue
            if (visited[newHeight][newRow][newCol]) continue
            if (box[newHeight][newRow][newCol] == -1) continue

            q.add(Triple(newHeight, newRow, newCol))
            visited[newHeight][newRow][newCol] = true
        }
    }

    return if (checkBox()) -1 else count
}

fun checkBox(): Boolean {
    for (i in 0 until h) {
        for (j in 0 until n) {
            for (k in 0 until m) {
                if (!visited[i][j][k] && box[i][j][k] != -1) return true
            }
        }
    }

    return false
}