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

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

7569번: 토마토

 

난이도 : 골드5
태그 : 그래프탐색, 너비우선탐색, 그래프이론

 

 

설명

이전의 포스팅했던 백준 7576번 토마토는 한 층인 평면(x, y축)으로만 이루어졌던과 달리,

7569번 토마토는 복수의 층으로 입체(x,y,z)로 이루어져 있는게 차이점입니다.

 

이전 포스팅의 코드를 베이스로 약간 변형을 주어 3차원 BFS로 풀이할 수 있으며,

이전 포스팅의 내용이 궁금하신 분은 아래 링크를 참고해주세요.

 

2022.06.22 - [코딩테스트 & 알고리즘/Kotlin] - [백준 7576번] [Kotlin] 토마토

[백준 7576번] [Kotlin] 토마토

 

 

 

소스코드

좌표를 담을 데이터 클래스와 방향 선언

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


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)

 

각 좌표를 담을 Node 클래스를 선언합니다. 기존 x, y층에 이어 z축(층) 까지 포함되어 있습니다.

 

방향을 도와줄 dx, dy에 이어 dz도 선언합니다.

 

인풋값 저장

val br = BufferedReader(InputStreamReader(System.`in`))
val mn = br.readLine()!!.split(" ") // m, n 순으로 입력받음
val n = mn[1].toInt()
val m = mn[0].toInt()
val h = mn[2].toInt()

var day = 0

val map = Array(n) { Array(m) { Array(h) { 0 } } }

val startNodes: Queue<Node> = LinkedList()

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

            map[x][y][z] = st.nextToken().toInt()
            if (map[x][y][z] == 1) {
                startNodes.offer(Node(x, y, z))
            }
        }
    }
}

bufferedReader와 StringTokenizer를 이용하여 인풋값들을 저장합니다.

단, 토마토가 있을 경우 startNode에 저장해줍니다.

 

 

BFS

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 || map[nx][ny][nz] == 1 || map[nx][ny][nz] == -1)
            continue

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

이제 3차원 맵을 대상으로 BFS를 하면 됩니다.

 

하나씩 보겠습니다.

 

 

val q: Queue<Node> = LinkedList()
startNodes.forEach { q.offer(it) }

q.offer(Node(-1, -1, -1))

토마토가 있는 곳을 시작으로 BFS를 실시하여야 하니,

토마토의 위치를 저장했던 startNode의 값들을 빼내어 큐에 넣습니다.

 

이후 한 사이클이 돌았다는 것을 표시하기 위해 -1,-1,-1 이라는 좌표를 넣어줍니다.

 

 

 

val target = q.poll()

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

다음은 while문 안쪽으로 들어갑니다.

 

큐에서 값을 하나 빼와 한 사이클이 돌았다는 것을 의미하는 (-1,-1,-1)좌표가 나오면

날짜값을 담고있는 day 변수를 +1만큼 늘려줍니다.

이후, 한 사이클이 돌았다는 것은 곧 지금 현재 한 사이클만의 원소가 큐에 담겨있다는 의미이므로,

다시 큐에 (-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 || map[nx][ny][nz] == 1 || map[nx][ny][nz] == -1)
        continue

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

이후, 상-하, 동-서-남-북 방향으로 해당 좌표가 방문하지 않은 곳이라면 방문처리를 해주고 큐에 넣습니다.

 

 

출력

map.forEach { it ->
    it.forEach { it2 ->
        it2.forEach { it3 ->
            if (it3 == 0) {
                println(-1)
                return
            }
        }
    }
}

println(day - 1)

만약, 토마토가 익지 않은 지점(0)이 있다면 -1을 출력하고, main 함수를 종료합니다.

 

그렇지 않다면 토마토가 익는데 걸린 시간을 출력합니다.

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.Queue
import java.util.StringTokenizer

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


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)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val mn = br.readLine()!!.split(" ") // m, n 순으로 입력받음
    val n = mn[1].toInt()
    val m = mn[0].toInt()
    val h = mn[2].toInt()

    var day = 0

    val map = Array(n) { Array(m) { Array(h) { 0 } } }

    val startNodes: Queue<Node> = LinkedList()

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

                map[x][y][z] = st.nextToken().toInt()
                if (map[x][y][z] == 1) {
                    startNodes.offer(Node(x, y, z))
                }
            }
        }
    }

    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 || map[nx][ny][nz] == 1 || map[nx][ny][nz] == -1)
                continue

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

    map.forEach { it ->
        it.forEach { it2 ->
            it2.forEach { it3 ->
                if (it3 == 0) {
                    println(-1)
                    return
                }
            }
        }
    }

    println(day - 1)
}

 

 

후기

분명 풀었던 문제였는데, 풀지 않았다 되있어서 의아했더니

 

알고보니 기존 문제는 2차원 BFS, 현재 문제는 3차원 BFS로 다른 문제였습니다.

 

기존에 작성한 코드가 있으니, 간단한 수정만 거쳐 그리 어렵지 않게 풀었던 것 같습니다.