백준 - 2636 치즈 (코틀린)

[문제]

https://www.acmicpc.net/problem/2636

2636번: 치즈

[풀이]

치즈의 깊숙한 정도마다 차이가 있는 것이 아니기 때문에 치즈가 있는 부분에 바로 bfs를 통해 치즈가 녹을 경과일을 구할 수 없다.

치즈의 가장자리 부분만 먼저 체크를 하고 경과일을 저장하고, 그 가장자리 부분 탐색이 끝나면 그 다음 안 쪽 부분을 체크를 하고 경과일+1을 저장하는 식으로 접근했다.

판의 가장자리는 무조건 치즈가 없기 때문에 (0,0)에서 치즈 가장자리를 구하는 bfs를 돌린다. 만약 탐색 중 다음 이동할 자리에 치즈가 있다면 그 부분은 1(경과일)을 저장하여 가장자리라는 표시를 해두고 또 다른 큐에 저장을 하고 넘어간다.

위의 단계를 지나면 치즈 가장자리의 좌표를 얻을 수 있고 이는 큐에 저장되어 있다. 큐를 이용해서 또 bfs를 돌리는데 만약 다음 이동할 자리가 치즈라면 경과일 + 1을 저장하고, 방문하지 않았는데 치즈가 아니라면 치즈에 둘러싸여 처음 단계에서 체크를 못한 부분이므로 그 때의 좌표를 통해 처음 단계의 bfs를 돌린다. 이 때 경과일을 기억하고 1 대신에 경과일을 저장해주면 해당 시점에서의 경과일을 알 수 있다.

즉 빈공간을 찾는 bfs와 현재 치즈의 가장자리를 찾는 bfs를 이용하여 경과일을 알아낼 수 있다.

[코드]

import java.util.*

private var n = 0
private var m = 0
private lateinit var cheeses : Array<IntArray>
private lateinit var visited : Array<IntArray>
private lateinit var cheeseQueue : Queue<Pair<Int,Int>>
private val dx = listOf(1,-1,0,0)
private val dy = listOf(0,0,1,-1)
private var days = 0
fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    br.readLine().split(" ").map { it.toInt() }.apply {
        n = this[0]
        m = this[1]
    }

    cheeses = Array(n){ IntArray(m) }
    visited = Array(n){ IntArray(m){ -1 } }
    cheeseQueue = ArrayDeque()
    repeat(n){
        cheeses[it] = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }
    bfs(Pair(0,0),0)
   cheeseBfs()
    var cnt = 0
    visited.forEach { v ->
        v.forEach {
            if(it == days)
                cnt += 1
        }
    }
    bw.write("${days}\n${cnt}")
    bw.flush()
    bw.close()
}
private fun bfs(point: Pair<Int,Int>,cur : Int){
    val queue : Queue<Pair<Int,Int>> = ArrayDeque()
    queue.add(point)
    visited[point.first][point.second] = 0
    while (queue.isNotEmpty()){
        val (x,y) = queue.poll()
        for(i in 0 .. 3){
            val nx = x + dx[i]
            val ny = y + dy[i]
            if(nx <0 || ny < 0 || nx >= n || ny >= m) continue
            if(visited[nx][ny] == cur) continue
            if(visited[nx][ny] == cur +1) continue
            if(cheeses[nx][ny] == 1) {
                visited[nx][ny] = cur + 1
                cheeseQueue.add(Pair(nx,ny))
                continue
            }
            visited[nx][ny] = cur
            days = Math.max(cur,days)
            queue.add(Pair(nx,ny))
        }
    }
}
private fun cheeseBfs(){
    while (cheeseQueue.isNotEmpty()){
        val (x,y) = cheeseQueue.poll()
        days = Math.max(visited[x][y],days)
        for(i in 0 .. 3) {
            val nx = x + dx[i]
            val ny = y + dy[i]
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue
            if (visited[nx][ny] == visited[x][y]) continue
            if (cheeses[nx][ny] == 1 && visited[nx][ny] == -1) {
                visited[nx][ny] = visited[x][y] + 1
                cheeseQueue.add(Pair(nx, ny))
                continue
            }
            if (cheeses[nx][ny] == 0 && visited[nx][ny] == -1) {
                visited[nx][ny] = visited[x][y]
                bfs(Pair(nx, ny), visited[x][y])
            }
        }
    }
}