[백준] 2636번 치즈

2636번 치즈

접근방법

최대 길이가 가로,세로 100이기 때문에 완전탐색 방법을 택했다.

그래프를 만들 때, 1은 cheese로 보고 풀었고 0은 inner와 outer로 구분하여 풀기로 하였습니다. 처음에 값을 받을 때 모든 0을 inner로 만들었습니다.

1. Mark 함수
   (0,0)에서 치즈가 아닌 0인 영역을 가며 모두 outer로 바꿔주었습니다.

2. MeltCheese 함수
   height, widht순으로 그래프를 순회하며 치즈이면서 Outer와 닿는 row,col을 구해 list에 저장했습니다.
   그래프 순회 후에 list의 있는 point를 이용해 그래프에 접근하여 outer로 변환하였습니다.
   그리고 지난 시간과 현재 남은 치즈수를 pair로 만들어 다른 answer list에 저장했습니다.

   발견하자마자 바꾸지 않은 이유는, 값이 변하며 순회도중 계속 0으로 만들기 때문입니다.

3. (1 - 2)를 반복하여 모든 치즈가 녹으면
   answer list의 lastIndex에서 걸린 시간, lastIndex - 1에서 남은 치즈수를 가져와 출력하였습니다.

시간 복잡도

O(N^3): MeltCheese 과정이 N^2이고 위의 (1-2)를 반복하는 과정이 최대 N/2이므로 O(N^3)이 나온다.

Code

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

class IO2636 {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private val bw = BufferedWriter(OutputStreamWriter(System.out))

    fun getNM() = br.readLine().split(" ").map { it.toInt() }
    fun getRows() = br.readLine().split(" ")
    fun write(message: String) = bw.write(message)
    fun flush() = bw.flush()
    fun close() = bw.close()
}

fun main() {
    val io = IO2636()
    val (height, width) = io.getNM()
    val graph = Array(height) { arrayListOf<Short>() }
    var cheeseCount = 0
    repeat(height) {
        graph[it].addAll(io.getRows().map { e ->
            if (e == "1") {
                cheeseCount++
                (1)
            }
            else (2)
        })
    }

    val checkInside = { point: Point -> point.x in (0 until width) && point.y in (0 until height) }

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

    fun markOuter() {
        val q: Queue<Point> = LinkedList()
        q.add(Point(0,0))
        var visited = getVisited(height, width)
        while (q.isNotEmpty()) {
            val point = q.poll()
            val element = graph[point.y][point.x]
            if (element == (2).toShort()) {
                graph[point.y][point.x] = (0)
            }
            for (idx in 0..3) {
                val newPoint = Point(point.y + dy[idx], point.x + dx[idx])
                if (checkInside(newPoint) && !visited[newPoint.y][newPoint.x] && graph[newPoint.y][newPoint.x] != (1).toShort()) {
                    q.add(newPoint)
                    visited[newPoint.y][newPoint.x] = true
                }
            }
        } // 공기 외부, 공기 내부, 치즈 구분 완료
    }

    fun meltCheese(): Int {
        val meltingList = mutableListOf<Point>()
        var melting = 0
        for (row in 0 until height) {
            for (col in 0 until width) {
                if (graph[row][col] == (1).toShort()) {
                    for (idx in 0..3) {
                        val newPoint = Point(row + dy[idx], col + dx[idx])
                        if (checkInside(newPoint) && graph[newPoint.y][newPoint.x] == (0).toShort()) {
                            meltingList.add(Point(row, col))
                            melting++
                            break
                        }
                    }
                }
            }
        }
        meltingList.forEach {
            graph[it.y][it.x] = (0)
        }
        return melting
    }

    var hour = 0
    val ansList = mutableListOf(hour to cheeseCount)
    while (cheeseCount > 0) {
        markOuter()
        val count = meltCheese()
        hour++
        cheeseCount -= count
        ansList.add(hour to cheeseCount)
    }

    io.write(ansList[ansList.lastIndex].first.toString() + "\n")
    io.write(ansList[ansList.lastIndex-1].second.toString())
    io.flush()
    io.close()
}

fun getVisited(height: Int, width: Int): Array<Array<Boolean>> {
    return Array(height) { Array(width) { false } }
}

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