7569번: 토마토

문제 출처 : https://www.acmicpc.net/problem/7569

 

언어 : Kotlin

 

문제 설명 :

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

입력 :

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

출력 :

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
5 3 1 0 -1 0 0 0 -1 -1 0 1 1 0 0 0 1 1	-1
5 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0	4
4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 1 -1	0

 

풀이 : 

3차원 배열이므로 좌표 축 3개, 방향도 3개로 구성한다.

Node(x y z), dx, dy, dz

 

3차원 맵을 대상으로한 BFS.

토마토가 있는 곳 기준으로 시작하여 BFS를 실행해야한다.

값들을 입력할때 startNodes라는 Queue에 토마토의 좌표값을 저장한다.

 

이후 BFS할 때 startNode의 값들을 빼내어 BFS 큐에 넣는다. 또한, 한 사이클을 돌았다는 것을 확인하기 위해 -1, -1, -1이라는 좌표를 넣는다.

 

BFS 큐에서 값을 하나 빼어 target으로 지정.

target의 x, y, z 값이 -1이라면 한 사이클을 돌았다는 것으로 결과값 day++

또한, 한 사이클을 돌았다는 것은 한 사이클만의 원소가 큐에 담긴 것이므로 다시 큐에 -1 -1 -1 좌표를 추가한다.

 

문제에서 제시한대로 위 아래 좌 우 앞 뒤로 방문하지 않은 곳이라면 방문 처리후 큐에 넣는다.

토마토가 익지 않은 곳이 있다면 day = 0

이후 걸린 시간 day - 1을 출력.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

data class Node(val x: Int, val y: Int, val z: Int)

lateinit var box: Array<Array<IntArray>>
val dx = arrayOf(0, 0, 1, -1, 0, 0)
val dy = arrayOf(1, -1, 0, 0, 0, 0)
val dz = arrayOf(0, 0, 0, 0, 1, -1)
var day = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (m, n, h) = readLine().split(" ").map { it.toInt() }
    box = Array(n) { Array(m) { IntArray(h) } }
    val startNodes: Queue<Node> = LinkedList()

    repeat(h) { z ->
        repeat(n) { x ->
            val st = StringTokenizer(readLine(), " ")

            repeat(m) { y ->
                box[x][y][z] = st.nextToken().toInt()
                if (box[x][y][z] == 1) startNodes.offer(Node(x, y, z))
            }
        }
    }

    bfs(startNodes, n, m, h)
    
    box.forEach { arr ->
        arr.forEach { ints ->
            ints.forEach { num ->
                if (num == 0) day = 0
            }
        }
    }
    
    bw.write("${day - 1}")
    bw.flush()
    bw.close()
}

fun bfs(startNodes: Queue<Node>, n: Int, m: Int, h: Int) {
    val q: Queue<Node> = LinkedList()
    startNodes.forEach { q.offer(it) }
    q.offer(Node(-1, -1, -1))

    while (q.isNotEmpty()) {
        val target = q.poll()

        if (target.x == -1 && target.y == -1 && target.z == -1) {
            day++
            if (q.isNotEmpty()) q.offer(Node(-1, -1, -1))
        }

        for (i in 0 until 6) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]
            val nz = target.z + dz[i]

            if (nx !in 0 until n || ny !in 0 until m || nz !in 0 until h ||
                box[nx][ny][nz] == 1 || box[nx][ny][nz] == -1) {
                continue
            }

            box[nx][ny][nz] = 1
            q.offer(Node(nx, ny, nz))
        }
    }
}