[백준] 7576번: 토마토 - Kotlin[코틀린]

문제

 

7576번: 토마토

 

---

풀이

 

 토마토가 익는 과정은 동시에 일어나기 때문에 Queue를 이용한 BFS(너비 우선 탐색)으로 해결할 수 있다.

 

 배열을 입력 받아 익은 토마토(1)인 경우에는 Queue에 추가해준다. 익지 않은 토마토(0)인 경우에는 익지 않은 토마토의 개수를 확인하는 변수인 cnt를 증가시켜준다. 

 

 이제 BFS를 실행하면 된다. 큐에서 하나의 위치를 꺼내어 상하좌우를 탐색하며 익지 않은 토마토(0)를 만나게 되면 cnt를 1 감소시키고 배열에 현재 날짜 + 1을 대입 시켜준다. 탐색이 끝났을 때, cnt가 0이라면 모든 토마토가 익었으므로 최소 일수를 출력한다. 그렇지 않다면 모든 토마토가 익지 못하는 상황 -1을 출력한다.

 

---

코드

 

import java.util.*

data class Point(val x: Int, val y: Int)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val dx = arrayOf(1, 0, -1, 0)
    val dy = arrayOf(0, 1, 0, -1)

    var st = StringTokenizer(br.readLine())
    val (cols, rows) = arrayOf(st.nextToken().toInt(), st.nextToken().toInt())
    val arr = Array(rows) { IntArray(cols) }
    val queue : Queue<Point> = LinkedList()
    var cnt = 0 // 익지 않은 토마토의 개수

    for (i in 0 until rows) {
        st = StringTokenizer(br.readLine())
        for (j in 0 until cols) {
            arr[i][j] = st.nextToken().toInt()

            when (arr[i][j]) { // 익은 토마토는 큐에 추가, 익지 않은 토마토는 개수 증가
                1 -> queue.add(Point(i, j))
                0 -> cnt++
            }
        }
    }

    fun bfs() : Int {
        var day = 0

        while(queue.isNotEmpty()) {
            val (tx, ty) = queue.poll()
            day = arr[tx][ty]

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

                if(nx<0||ny<0||nx>=rows||ny>=cols) continue
                if(arr[nx][ny]!=0) continue

                cnt--
                queue.add(Point(nx, ny))
                arr[nx][ny] = day + 1
            }
        }

        return if(cnt == 0) day - 1
        else -1 // 익지 않은 토마토가 남아 있는 경우
    }

    bw.write("${bfs()}")
    bw.flush()
    bw.close()
    br.close()
}