[백준] 7569 (토마토)

#1 알고리즘

그래프 - 너비 우선 탐색 (BFS, Breadth-First Search)

 

#2 코드 - 코틀린

import java.util.*

var X = -1 // M
var Y = -1 // N
var Z = -1 // H
lateinit var tomatoes: Array<Array<Array<Int>>>

const val RIPE_TOMATO = 1
const val UNRIPE_TOMATO = 0

const val RESULT_CANT_RIPEN_ALL = -1

fun main() {
    val boxSizes = readln().split(" ")
    X = boxSizes[0].toInt()
    Y = boxSizes[1].toInt()
    Z = boxSizes[2].toInt()

    tomatoes = Array(Z) { Array(Y) { Array(X) { -2 } } }
    val initialRipeTomatoes = ArrayList<Triple<Int, Int, Int>>()
    for (z: Int in 0..<Z) {
        for (y: Int in 0..<Y) {
            val row = readln().split(" ")

            for (x: Int in 0..<X) {
                tomatoes[z][y][x] = row[x].toInt()

                if (row[x].toInt() == RIPE_TOMATO) {
                    initialRipeTomatoes.add(Triple(z, y, x))
                }
            }
        }
    }

    bfs(initialRipeTomatoes)

    var max = -1
    for (z: Int in 0..<Z) {
        for (y: Int in 0..<Y) {
            val row = tomatoes[z][y]

            for (x: Int in 0..<X) {
                val dayToRipen = row[x]

                if (dayToRipen == UNRIPE_TOMATO) {
                    println(RESULT_CANT_RIPEN_ALL)
                    return
                }

                if (max < dayToRipen) {
                    max = dayToRipen
                }
            }
        }
    }

    /* bfs()에서 initialRipeTomatoes들에 1을 부여한 시점은 관찰 시작일이었음.
     * 관찰 시작일에 0이 아닌 1을 일괄적으로 부여했으므로,
     * 모든 값에 -1을 가해 출력해야 정확한 날짜 값이 나옴.
     */
    println(max - 1)
}


fun bfs(initialRipeTomatoes: ArrayList<Triple<Int, Int, Int>>) {
    val queue: Queue<Triple<Int, Int, Int>> = LinkedList()
    val visited = Array(Z) { Array(Y) { Array(X) { false } } }

    for (tomato in initialRipeTomatoes) {
        val z = tomato.first
        val y = tomato.second
        val x = tomato.third
        queue.add(Triple(z, y, x))
        visited[z][y][x] = true
        tomatoes[z][y][x] = 1 // 토마토 관찰 시작일을 1일로 침
    }

    while (queue.isNotEmpty()) {
        val prev = queue.poll()
        val prevZ = prev.first
        val prevY = prev.second
        val prevX = prev.third

        for (next in getNexts(prev)) {
            val nextZ = next.first
            val nextY = next.second
            val nextX = next.third

            if (!visited[nextZ][nextY][nextX]) {
                queue.add(Triple(nextZ, nextY, nextX))
                visited[nextZ][nextY][nextX] = true
                tomatoes[nextZ][nextY][nextX] = tomatoes[prevZ][prevY][prevX] + 1
            }
        }
    }
}

fun getNexts(prev: Triple<Int, Int, Int>): List<Triple<Int, Int, Int>> {
    val prevZ = prev.first
    val prevY = prev.second
    val prevX = prev.third

    val candidates = listOf(
        Triple(prevZ - 1, prevY, prevX),
        Triple(prevZ + 1, prevY, prevX),
        Triple(prevZ, prevY - 1, prevX),
        Triple(prevZ, prevY + 1, prevX),
        Triple(prevZ, prevY, prevX - 1),
        Triple(prevZ, prevY, prevX + 1),
    )

    val nexts = ArrayList<Triple<Int, Int, Int>>()
    for (candidate in candidates) {
        val candidateZ = candidate.first
        val candidateY = candidate.second
        val candidateX = candidate.third

        if ((candidateZ in 0..<Z) && (candidateY in 0..<Y) && (candidateX in 0..<X) && (tomatoes[candidateZ][candidateY][candidateX] == UNRIPE_TOMATO)) {
            nexts.add(candidate)
        }
    }
    return nexts
}