[백준] 7576. 토마토 (Kotlin)

문제 : https://www.acmicpc.net/problem/7576

7576번: 토마토

 

 

풀이

// [백준] 7576. 토마토 (Kotlin)
import java.util.*

fun main() = with(System.`in`.bufferedReader()){
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt() // 세로 칸 수
    val m = st.nextToken().toInt() // 가로 칸 수
    val tomato = Array(m+2){Array(n+2){-1} } // 토마토 창고
    var count = -1 // 걸리는 날짜
    var con = true // 종료 여부

    // 입력
    for(i in 1 until m+1){
        st = StringTokenizer(readLine())
        for(j in 1 until n+1){
            tomato[i][j] = st.nextToken().toInt()
        }
    }

    while(con){
        con = false
        val tmp = arrayListOf<Pair<Int,Int>>() // 익은 토마토 저장

        // 하나씩 확인
        for(i in 1 until m+1){
            for(j in 1 until n+1){
                // 익은 토마토라면
                if(tomato[i][j] == 1){
                    tmp.add(Pair(i,j))
                }
                // 익지 않은 토마토일 때
                else if(tomato[i][j] == 0){
                    con = true // 익지않은 토마토가 하나라도 있으면 계속 진행

                    // 상하좌우에 토마토가 없어서 익을수 없으면
                    if(tomato[i][j - 1] == -1 && tomato[i][j + 1] == -1
                        && tomato[i - 1][j] == -1 && tomato[i + 1][j] == -1){
                            println(count)
                            return@with
                    }
                }
            }
        }

        // 하루가 지나면 상하좌우 토마토 익음
        while(tmp.isNotEmpty()) {
            val i = tmp[0].first
            val j = tmp[0].second
            if (tomato[i][j - 1] == 0) tomato[i][j - 1] = 1
            if (tomato[i][j + 1] == 0) tomato[i][j + 1] = 1
            if (tomato[i - 1][j] == 0) tomato[i - 1][j] = 1
            if (tomato[i + 1][j] == 0) tomato[i + 1][j] = 1
            tmp.removeAt(0)
        }
        count++
    }

    println(count)

//    // 창고 확인
//    tomato.forEach { println(it.contentToString()) }
}

오답1 (시간 초과)

처음에 떠올린 기본 구조는 익은 토마토는 상하좌우에 영향을 주므로 

계산하기 편하게 토마토의 정보를 n+2, m+2 크기의 배열에 담은 후

전체원소를 탐색하여 익은 토마토가 있으면 상하좌우 토마토를 다음날 익을 토마토 큐에 저장후 다음날이 될때마다

큐에 저장된 토마토들을 익었다고 처리하고, 다시 이 과정을 반복했다.

 

또한 익지 않은 토마토가 상하좌우에 -1로 갇혀있다면 익을 수 없을 것이라 판단해서 그 경우에 -1을 리턴하도록 하였다.

 

하지만 시간초과가 발생했고 M,N의 최대크기가 1000이기 때문에 더 효율적인 방법이 필요하다는 것을 깨달았다.

 

// [백준] 7576. 토마토 (Kotlin)
import java.util.*

fun main() = with(System.`in`.bufferedReader()){
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt() // 세로 칸 수
    val m = st.nextToken().toInt() // 가로 칸 수
    val tomato = Array(m+2){Array(n+2){-1} } // 토마토 창고
    var count = -1 // 걸리는 날짜
    var queue = arrayListOf<Pair<Int,Int>>() // 익은 토마토 저장 (큐)

    // 입력
    for(i in 1 until m+1){
        st = StringTokenizer(readLine())
        for(j in 1 until n+1){
            tomato[i][j] = st.nextToken().toInt()
        }
    }

    // 하나씩 확인
    for(i in 1 until m+1){
        for(j in 1 until n+1){
            // 익은 토마토라면
            if(tomato[i][j] == 1){
                queue.add(Pair(i,j))
            }
            // 익지 않은 토마토일 때
            else if(tomato[i][j] == 0){
                // 상하좌우에 토마토가 없어서 익을수 없으면 -1 출력
                if(tomato[i][j - 1] == -1 && tomato[i][j + 1] == -1
                    && tomato[i - 1][j] == -1 && tomato[i + 1][j] == -1){
                        println(count)
                        return@with
                }
            }
        }
    }

    // 하루가 지나면 상하좌우 토마토 익음
    while(queue.isNotEmpty()) {
        count++
        val tmp = arrayListOf<Pair<Int,Int>>() // 익은 토마토 저장 (큐)
        tmp.addAll(queue)
        queue = arrayListOf<Pair<Int,Int>>()

        for(q in 0 until tmp.size){
            val i = tmp[q].first
            val j = tmp[q].second
            if (tomato[i][j - 1] == 0) {
                tomato[i][j - 1] = 1
                queue.add(Pair(i,j-1))
            }
            if (tomato[i][j + 1] == 0) {
                tomato[i][j + 1] = 1
                queue.add(Pair(i,j+1))
            }
            if (tomato[i - 1][j] == 0) {
                tomato[i - 1][j] = 1
                queue.add(Pair(i-1,j))
            }
            if (tomato[i + 1][j] == 0) {
                tomato[i + 1][j] = 1
                queue.add(Pair(i+1,j))
            }
        }
    }

    println(count)

//    // 창고 확인
//    tomato.forEach { println(it.contentToString()) }
}

오답2 (반례)

그 이후로 떠올린 방법은

전체원소를 탐색하여 익은 토마토가 있으면 상하좌우 토마토를 다음날 익을 토마토 큐에 저장후 다음날이 될때마다

큐에 저장된 토마토들을 익었다고 처리하고, 다시 이 과정을 반복하는 구조에서

 

저 과정을 한번만 하고 그 이후로 전체원소를 다 탐색할 필요 없이 다음날 익은 토마토들만 처리해주면 된다는 것을 깨달았다.

 

시간 문제는 해결하였으나

95%를 넘어가는 시점에서 오답처리 되었다.

그래서 반례를 계속 찾아보았는데, 토마토가 익을 수 없는 조건처리가 문제였다.

 

예를 들어

 

5 1

1 0 -1 0 0

 

라는 입력값이 들어온다면 m+2 , n+2 처리했으므로 실제적인 창고의 모습은

 

-1 -1 -1 -1 -1 -1 -1

-1  1  0  -1 0  0  -1

-1 -1 -1 -1 -1 -1 -1

 

이런 모양일 것이다.

여기서 빨간색으로 표시한 0 들은 익을수 없는 조건 (상하좌우 -1)를 만족하지 않지만 눈으로 확인해보면 분명 익지 않는다.

 

// [백준] 7576. 토마토 (Kotlin)
import java.util.*

fun main() = with(System.`in`.bufferedReader()){
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt() // 세로 칸 수
    val m = st.nextToken().toInt() // 가로 칸 수
    val tomato = Array(m+2){Array(n+2){-1} } // 토마토 창고
    var count = -1 // 걸리는 날짜
    var queue = arrayListOf<Pair<Int,Int>>() // 다음날 익을 토마토 저장

    // 입력
    for(i in 1 until m+1){
        st = StringTokenizer(readLine())
        for(j in 1 until n+1){
            tomato[i][j] = st.nextToken().toInt()
        }
    }

    // 하나씩 확인
    for(i in 1 until m+1){
        for(j in 1 until n+1){
            // 익은 토마토라면 큐에 추가
            if(tomato[i][j] == 1){
                queue.add(Pair(i,j))
            }
        }
    }

    // 하루가 지나면 상하좌우 토마토 익음, 더이상 익을게 없을때 까지 반복
    while(queue.isNotEmpty()) {
        count++ // 다음날
        val tmp = arrayListOf<Pair<Int,Int>>() // 지금 익은 토마토 저장
        tmp.addAll(queue) // 지금 익은 토마토 불러옴(queue)
        queue = arrayListOf<Pair<Int,Int>>() // 다음날 익을 토마토 저장 위해 초기화

        // 상하좌우 다음날 익을 토마토 큐에 저장
        for(q in 0 until tmp.size){
            val i = tmp[q].first
            val j = tmp[q].second
            if (tomato[i][j - 1] == 0) {
                tomato[i][j - 1] = 1
                queue.add(Pair(i,j-1))
            }
            if (tomato[i][j + 1] == 0) {
                tomato[i][j + 1] = 1
                queue.add(Pair(i,j+1))
            }
            if (tomato[i - 1][j] == 0) {
                tomato[i - 1][j] = 1
                queue.add(Pair(i-1,j))
            }
            if (tomato[i + 1][j] == 0) {
                tomato[i + 1][j] = 1
                queue.add(Pair(i+1,j))
            }
        }
    }

    // 더이상 익을 수 있는 것이 없을 때, 익지 않은 토마토가 있다면
    for (i in 1 until m+1){
        for(j in 1 until n+1){
            if(tomato[i][j] == 0) {
                println(-1)
                return
            }
        }
    }

    println(count)

//    // 창고 확인
//    tomato.forEach { println(it.contentToString()) }
}

최종코드

그래서 굳이 저 조건으로 판별하지 않고

반복문이 종료되었을 때(더이상 익을 수 있는 토마토가 없을 때), 배열에 0이 하나라도 존재한다면 아직 익지 않는 토마토가 존재하는 것이므로 그 경우에 -1을 출력해주었다.