백준 2638 치즈 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/2638

2638번: 치즈

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

 

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

 

<그림 2>

 

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션
• 깊이 우선 탐색

풀이

간단한 시뮬레이션 문제.

외부와 접촉하는 칸을 추려내는 빙산,치즈, 바이러스 이런 문제들은 보통 그래프의 크기를 1씩 키워서 가상의 칸부터 bfs를 돌리는 테크닉이 사용되는데, 이 문제는 가장자리에는 치즈가 놓이지 않는다는 조건이 있으니 시원하게 0,0부터 bfs를 돌리면 된다.

 

근데 왜 0,0부터 bfs를 돌릴까?

사실 0,0이건 0,1이건 상관 없다.

그냥 치즈가 아닌 바깥 칸에서 bfs를 돌리는 것이다.

0,0에서 아무 조건 없이 bfs로 그래프를 탐색한다면 모든 칸을 돌게 될 것이다.

이때, 우리는 이미 방문한 칸을 재방문하는 중복을 제거하기 위해 visited를 체크한다.

이 테크닉을 응용한다면?

우리는 치즈가 외부에 몇 칸이나 노출되어 있는지 찾아야 한다.

그럼 Bfs를 돌리면서, 다음 칸이 치즈이건 말건 방문 횟수를 1 올려주고, 만약 치즈라면 이동하지 않고, 치즈가 아니라면 이동한다.

그럼 우린 외부 칸에서 치즈로 들어가는 개수를 알 수 있고 이는 즉 치즈가 외부에 몇 칸이나 노출되어 있는지를 의미한다.

재방문도 제거할 수 있다. 치즈이건 말건 방문 횟수를 1 올리기 때문에 치즈 외부 칸에 방문 횟수가 1보다 높다면 더 이상 방문하지 않으면 된다.

정리하면 다음과 같다.

1. 치즈 외부 칸 (0,0)에서 bfs 한 타임 돌린다.

2. 다 돌면 치즈가 외부와 몇 칸이나 접촉하는지 알 수 있다.

3. 그래프를 탐색하며 해당 칸이 치즈이면 몇 칸 접촉했는지 확인하여 2칸 이상이면 제거

4. 제거하고 남아있는 치즈가 있다면 다시 1번 과정으로 돌아가서 bfs를 돌린다.

5. 남아있는 치즈가 없다면 bfs를 돌린 횟수를 리턴하고 종료한다. 

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getStr() = br.readLine().trim()
fun getInt() = br.readLine().trim().toInt()

lateinit var graph: Array<IntArray>
val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(1,0),
    arrayOf(0,-1),
    arrayOf(-1,0),
)

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n,m) = getIntList()
    graph = Array(n){ getIntList().toIntArray() }
    //solve, output
    write("${bfs(n,m)}")

    close()
}

fun bfs(n: Int, m: Int): Int{
    var time = 0
    while(true){
        val visited = Array(n){IntArray(m)}
        val q: Queue<Pair<Int,Int>> = LinkedList()
        q.add(Pair(0,0))
        visited[0][0] = 1
        while(q.isNotEmpty()){
            val (r,c) = q.poll()
            for(i in 0 until 4){
                val nr = r+dir[i][0]
                val nc = c + dir[i][1]
                if(nr !in 0 until n || nc !in 0 until m) continue
                visited[nr][nc]= visited[nr][nc]+1
                if(visited[nr][nc]>1 || graph[nr][nc]==1) continue
                q.add(Pair(nr,nc))
            }
        }
        time++
        var oneCount = 0
        for(r in 0 until n){
            for(c in 0 until m){
                if(graph[r][c] ==1) {
                    if(visited[r][c]>=2){
                        graph[r][c] = 0
                    }else{
                        oneCount++
                    }
                }
            }
        }
        if(oneCount==0) break
    }
    return time
}