[BOJ] 7576

[HyomK]

백준 7576 토마토
[문제유형] 그래프 탐색
https://www.acmicpc.net/problem/7576

포인트

일반적인 그래프 탐색의 경우 한번의 탐색을 하기 위해 visited 체커를 이용하지만
이 문제의 경우 여러번의 탐색을 해야 한다.
특정 노드는 상하좌우 4가지 인접 노드를 갖고 있다. 탐색 조건은 상태가 0 인 인접 노드에 대해 깊이 탐색을 진행한다.

Tomato 클래스의 day에는 결국 몇번째 날에 토마토가 익었는 지 누적된 값이 들어가게 된다
마지막으로 큐에서 꺼낸 tomato가 가장 늦게 익은 것이고 그 날짜가 최소로 걸리는 날짜가 된다

핵심코드

    data class Tomato(val x: Int, val y: Int, val day: Int)

    fun changeTomato() {
        while (queue.isNotEmpty()) {
            val cur = queue.poll()
            minDay = cur.day
            repeat(4) {
                val nx = cur.x + dx[it]
                val ny = cur.y + dy[it]

                if (nx in 0..width && ny in 0..height) {
                    if (tomato[ny][nx] == 0) {
                        tomato[ny][nx] = 1
                        //새로 익은 토마토를 넣는다
                        queue.add(Tomato(nx, ny, cur.day + 1))
                    }
                }
            }
        }
    }