[Kotlin, G5] 백준 7569번 토마토

출처: unsplash.com

 

토마토(7569번)

Gold 5

#그래프 이론 #그래프 탐색 #너비 우선 탐색

 

문제 내용

 

문제 접근

비슷한 문제인 토마토(7576)와는 상자를 여러 개를 받아 3차원으로 작업해야 하는 것이 다르다.

입력을 받을 때, 미리 생성한 ArrayDeque에 1(익은 토마토)이 들어 있으면 x, y, z, 0을 리스트로 받아서 넣어 준다.

x, y, z는 익은 토마토의 좌표이고, 0은 경과한 날짜를 뜻한다. 나중에 0을 하나씩 더해 가면서 경과 날짜를 체크할 것이다.

3차원 리스트에 입력값을 모두 넣어 주고 나서, 토마토를 bfs를 이용해 현재 토마토의 위치를 담은 ArrayDeque에 있는 값을 하나씩 빼면서 뺀 값의 x, y, z에서 앞, 뒤, 오른쪽, 왼쪽, 위, 아래에 해당하는 토마토들을 확인해서 덜 익은 토마토(0)이면, 토마토

를 익은 상태(1)로 변경하고 큐에 이동한 x, y, z값에 이전에 ArrayDeque에서 뺀 값에 하루가 지났다는 뜻인 1을 더한 값을 4번째 추가값에 넣어서 ArrayDeque의 맨 앞에 넣어 준다.

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.ArrayDeque

private val queue = ArrayDeque<List<Int>>()
private var box = arrayOf<Array<MutableList<Int>>>()

private val dx = listOf(-1, 1, 0, 0, 0, 0)
private val dy = listOf(0, 0, -1, 1, 0, 0)
private val dz = listOf(0, 0, 0, 0, -1, 1)

private var currentDay = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (x, y, z) = readLine().split(" ").map { it.toInt() }
    box = Array(z) { Array(y) { mutableListOf() } }

    for (i in 0 until z) {
        for (j in 0 until y) {
            val tomato = readLine().split(" ").map { it.toInt() }
            box[i][j].addAll(tomato)

            for (k in tomato.indices) {
                if (tomato[k] == 1) {
                    queue.addFirst(listOf(k, j, i, 0))
                }
            }
        }
    }

    bfs()

    for (i in box.indices) {
        for (j in box[i].indices) {
            if (box[i][j].contains(0)) {
                currentDay = -1
                break
            }
        }
    }

    println(currentDay)
}

private fun bfs() {
    while (queue.isNotEmpty()) {
        val data = queue.removeLast()
        currentDay = data.last()

        find(data[0], data[1], data[2])
    }
}

private fun find(x: Int, y: Int, z: Int) {
    for (i in dx.indices) {
        val mx = x + dx[i]
        val my = y + dy[i]
        val mz = z + dz[i]

        if (mz in box.indices && my in box[0].indices && mx in box[0][0].indices) {
            if (box[mz][my][mx] == 0) {
                box[mz][my][mx] = 1
                queue.addFirst(listOf(mx, my, mz, currentDay + 1))
            }
        }
    }
}

 

문제 풀이

입력값을 저장할 3차원 리스트 box에 입력값을 저장하고, 초기의 익은 토마토의 좌표를 저장할 queue(ArrayDeque)를 생성해 준다.

익은 토마토의 좌표에서 위, 아래, 오른쪽, 왼쪽, 앞, 뒤에 해당하는 죄표들의 토마토의 값을 확인하기 위해 dx, dy, dz를 생성한다.

 

입력값을 box에 저장하고, queue에 초기의 익은 토마토의 위치를 저장하고 나면 bfs 함수를 수행한다.

bfs에서는 다른 문제에서 bfs를 구현하듯이 queue가 빌 때까지 반복해 주고, queue에서 뽑는 데이터는 현재 queue의 마지막 데이터를 뽑아 준다(이유는 나중에 설명).

현재 날짜를 data의 마지막 값으로 설정한다.

그다음 x, y, z값을 파라미터로 받는 find 함수를 수행한다.

 

find 함수에서는 dx, dy, dz를 반복문을 돌려 각각 이동한 값을 mx, my, mz를 생성해 주고 각 이동한 값이 3차원 리스트를 넘지 않는지 확인 후, 덜 익은 토마토(0)가 있으면 그 값을 1(익음)로 교체하고, 교체된 토마토의 좌표에 현재 날짜에 1을 더한 값을 queue의 첫 번째 값으로 넣어 준다.

queue에 첫 번째 값으로 넣어주는 이유는

첫 번째 값에 시간이 지나 익은 토마토의 좌표가 주어지고, 뒤로 갈수록 익은 지 오래된 토마토가 존재할 것이다.

막 익은 토마토가 나중에 빠질 것이고, 익은 지 오래된 토마토가 먼저 빠지게 될 것이다.

초기에 0일로 설정된 토마토가 먼저 빠지고 그다음 1일 차에 익은 토마토가 빠지는 식이다.

 

모든 토마토를 날짜 순서대로 빼고 나면 bfs가 종료되고, 최종적인 토마토가 모두 익는 데 걸린 날짜인 currentDay를 출력하면 정답이 된다.

하지만 한 가지를 고려해야 하는데, 날짜가 아무리 지나도 토마토가 안 익는 경우가 있을 수 있다.

2중 for문으로 3차원 리스트의 값들을 모두 확인해 주고, 하나라도 덜 익은 토마토(0)가 있으면 currentDay를 -1로 바꿔서 출력한다.

 

 

문제 해결 과정

비슷한 문제은 Gold 5의 토마토(7576번)를 해결한 사람이면 입력과 이동만 수정해 주면 꽁으로 해결할 수 있는 문제이다.

문제를 풀면서 크게 어려웠던 점은 없었다.

토마토 7576번을 해결하지 않은 사람들은 7576번을 먼저 해결하고 이 문제를 푸는 게 도움이 될 것이다. 7576번은 2차원 리스트만 쓰기에 더 쉽다.