백준 - 7569 토마토(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

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

 

[문제 설명]

3차원 배열에서 BFS 탐색하기

 

[접근 방법]

익은 토마토를 큐에 넣어놓고, BFS 주변 탐색을 하면 된다.

주변탐색을 하면서 만약 주변이 익은 토마토(1)이거나 토마토가 없으면(0) 그 쪽으로는 탐색이 불가능하다.

BFS 탐색이 끝나고 익은 개수를 전체 토마토 개수와 비교하여 같으면 모든 토마토가 익은 것이므로 날짜를 출력한다.

3차원 배열인 것만 제외하면 평소 하던 BFS와 다를 게 없는 문제다.

import java.util.LinkedList
import java.util.StringTokenizer

// 북, 동, 남, 서, 위, 아래
// 북남 이동 방향
val dy = intArrayOf(-1, 0, 1, 0, 0, 0)
// 동서 이동 방향
val dx = intArrayOf(0, 1, 0, -1, 0, 0)
// 고저 이동 방향
val dz = intArrayOf(0, 0, 0, 0, 1, -1)
fun main() {
    // 박스에 들어 있는 모든 토마토(익든 익지 않든) 개수
    var totalTomatoCnt = 0
    // 가로, 세로, 높이
    val (m, n, h) = readln().split(" ").map { it.toInt() }
    val map = Array(h) { Array(n) { IntArray(m) } }
    val visited = Array(h) { Array(n) { BooleanArray(m) } }
    // BFS를 위한 큐
    // 가로, 세로, 높이 좌표를 배열로 넣을 것임.
    val queue = LinkedList<IntArray>()

    // 토마토 상태 입력
    for (i in 0 until h) {
        for (j in 0 until n) {
            val st = StringTokenizer(readln())
            for (k in 0 until m) {
                val tomatoStatus = st.nextToken().toInt()
                map[i][j][k] = tomatoStatus

                // 토마토면 전체 토마토 개수 추가하고 방문처리
                if (tomatoStatus == 1 || tomatoStatus == 0) {
                    totalTomatoCnt++
                    // 익은 토마토면 큐에 넣어줌
                    if (tomatoStatus == 1) {
                        visited[i][j][k] = true
                        queue.offer(intArrayOf(i, j, k))
                    }
                }
            }
        }
    }

    // 현재 익은 토마토 개수
    var ripenTomato = queue.size
    // 모든 토마토가 전부 익었으면 0을 출력하고 프로그램을 종료한다.
    if (totalTomatoCnt == ripenTomato) {
        println(0)
        return
    } else if (ripenTomato == 0) {
        // 익은 토마토가 하나도 없으면 전부 익을 수가 없음
        println(-1)
        return
    }

    val result = getMaxCntAndDay(map, queue, visited, ripenTomato, totalTomatoCnt)
    // 최대한 익는데 걸린 시간
    val costDay = result[0]
    // 최대한 익힐 수 있는 토마토 개수
    val cntOfRipen = result[1]
    // 총 토마토개수와 최대한 익을 수 있는 개수가 같으면 날짜를 출력
    if (totalTomatoCnt == cntOfRipen) {
        println(costDay)
    } else {
        println(-1)
    }
}

// 최대 익힐 수 있는 토마토의 개수를 구하는 메서드
// 토마토 상태가 저장되어 있는 map, 익은 토마토가 들어있는 queue, 방문 여부를 체크할 visited, 현재 익은 개수를 나타내는 prevRipenCnt, 전체 토마토 개수 totalTomatoCnt,
// 리턴값 크기가 2인 배열. 0은 걸린 시간, 1은 익은 개수
private fun getMaxCntAndDay(map: Array<Array<IntArray>>,queue: LinkedList<IntArray>, visited: Array<Array<BooleanArray>>, prevRipenCnt: Int = 0, totalTomatoCnt: Int): IntArray {
    // 현재 익은 개수
    var currentRipenCnt = prevRipenCnt
    var day = 0
    while (queue.isNotEmpty()) {
        day++
        // 오늘 하루동안 주변을 익게할 토마토 개수
        val todayCnt = queue.size
        for (i in 0 until todayCnt) {
            // 현재 토마토
            val node = queue.poll()
            // 주변을 탐색
            for (dIdx in dy.indices) {
                if (node[0] + dz[dIdx] !in visited.indices
                    || node[1] + dx[dIdx] !in visited[0].indices
                    || node[2] + dy[dIdx] !in visited[0][0].indices) {
                    continue
                }

                val nextPosition = intArrayOf(node[0] + dz[dIdx], node[1] + dx[dIdx], node[2] + dy[dIdx])
                // 방문했던 토마토거나, 이미 익었거나, 토마토가 없으면 탐색안함
                if (visited[nextPosition[0]][nextPosition[1]][nextPosition[2]]
                    || map[nextPosition[0]][nextPosition[1]][nextPosition[2]] == 1
                    || map[nextPosition[0]][nextPosition[1]][nextPosition[2]] == -1) {
                    continue
                }
                // 토마토를 익히고, 좌표를 큐에 넣음
                currentRipenCnt++
                visited[nextPosition[0]][nextPosition[1]][nextPosition[2]] = true
                queue.offer(nextPosition)
            }
        }

        if (currentRipenCnt == totalTomatoCnt) {
            break
        }
    }

    return intArrayOf(day, currentRipenCnt)
}

 

 

[반성점]

처음에 문제를 이해하는데 은근 시간이 걸렸다.

하나의 층을 한 행씩 입력을 주는데 이해를 잘 못했다.

두번째로는 3차원 배열을 만들어본 적이 없어서 검색을 해봤다.

2차원 배열처럼 그냥 배열에 한 차원을 더해주면 되는 거라 생각보다 간단했다.

3차원 배열 잘 쓰일 일은 없겠지만, 다음엔 검색 안하고 바로 짜자