[백준] 7576 - 토마토

지금까지의 BFS 와는 달리 시작점이 여러 군데인 문제이다.
ArrayDeque 를 전역적으로 선언하고, 미리 시작할 데이터를 넣어놓은다음 BFS 를 시작하여 이를 처리하였다.

풀이

import java.util.StringTokenizer

/*
* 상하좌우 영향을 주니 x +- 1, y +- 1
* 다 익게 되는 최소 일 수를 구해야함 (상자 일부 칸에는 토마토가 없을 수도 있다.)
*
* 첫 줄 상자크기 M * N. 각각 2 이상 1000 이하
* 둘째 줄부터 N개의 줄에는 토마토의 정보.
* 하나의 줄에는 토마토의 상태가 M 개의 정수로 주어진다. 정수 1 = 익은토마토, 정수 0 = 안익은 토마토, 정수 -1 = 안들어가있는 토마토
*
* 각 토마토에 접근할때 소모된 날을 넣어줘야한다.
* -1 이거나 이미 익은 경우는 들어가지 않는다.
*
* 출력의 경우 처음부터 모두 익었으면 0, 모두 익히지 못하는 상황이면 -1을 출력.
* 그게 아니라면 최소 날짜를 출력
*
* 1인 경우 모두 한 번에 출발해야함.
*
* */

private val dx = intArrayOf(-1, 1, 0, 0)
private val dy = intArrayOf(0, 0, -1, 1)
private var row = 0
private var col = 0
private val arrayDeque = ArrayDeque<Pair<Int, Int>>()
private lateinit var tomatoBoxArr: Array<Array<Pair<Int, Int>>>

// first = ripe, second = day
private var printDay = 0
// 박스에 들어간 토마토 개수
private var boxInTomatoCount = 0

private const val IS_RIPE = 1
private const val IS_NOT_RIPE = 0
private const val IS_NOT_EXIST = -1

fun `7576-토마토`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val boxSizeToken = StringTokenizer(br.readLine())
    col = boxSizeToken.nextToken().toInt()
    row = boxSizeToken.nextToken().toInt()

    // 토마토가 익은 상태인경우 초기화함과 동시에 arrayDeque 에 넣어주기
    tomatoBoxArr = Array(row){ i ->
        val tomatoToken = StringTokenizer(br.readLine())
        Array(col){ j ->
            // 익은 토마토가 존재하면  arrayDeque 에도 추가.
            val tomato = tomatoToken.nextToken().toInt()
            if(tomato == IS_RIPE) arrayDeque.addLast(i to j)
            if(tomato != IS_NOT_EXIST) boxInTomatoCount++
            tomato to 0
        }
    }

    // 만약 arrayDeque 사이즈와 boxInTomatoCount 가 같으면 모두 익은 상태.
    if(arrayDeque.size == boxInTomatoCount){
        bw.write("0")
        bw.flush()
        bw.close()
        br.close()
        return
    }


    while (arrayDeque.isNotEmpty()){
        val location = arrayDeque.removeFirst()
        val x = location.first
        val y = location.second
        // 익은 것들은 박스에서 빼내줬다고 가정하여 -1 해주기
        boxInTomatoCount--

        for(i in 0 until 4){
            val nx = x + dx[i]
            val ny = y + dy[i]

            if(nx in 0 until row && ny in 0 until col && tomatoBoxArr[nx][ny].first == IS_NOT_RIPE){
                /*
                * 익은 상태로 변했으므로 날짜 증가, 배열[nx][ny] 의 ripe 및 day 변경 후 printDay 에 넣어주기
                * */
                val tomorrow = tomatoBoxArr[x][y].second + 1
                tomatoBoxArr[nx][ny] = IS_RIPE to tomorrow
                printDay = maxOf(printDay, tomorrow)
                arrayDeque.addLast(nx to ny)
            }
        }
    }

    // 박스 안의 남아있는 토마토가 0개면 모두 익어서 출하된 상태이다.
    if(boxInTomatoCount == 0){
        bw.write(printDay.toString())
    } else {
        // 박스 안의 남아있는 토마토가 0개를 넘으면 모두 익히지는 못한 상태이다.
        bw.write("-1")
    }

    bw.flush()
    bw.close()
    br.close()
}

후기

처음에는 printDay 를 tomorrow 로 바로 넣어줬지만, 이렇게 진행하는 경우 값이 덮어씌워질 수 있다는 것을 나중에 알아 고쳐썼다.

문제에 대한 풀이 방법은 쉽게 떠올랐지만, 정답을 도출해내는 것까지는 헷갈려서 생각보다 오래걸렸다.