백준 2638 치즈

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

이차원 배열에 치즈(1) 영역이 주어지고, 외부 영역(0)에 두 면 이상 접한 치즈는 시간마다 사라진다. 모든 치즈가 사라지는 시간을 구하는 문제이다.

주의해야 할 점은 <그림 2>처럼 치즈에 둘러싸인 빈 영역은 외부 영역으로 취급하지 않는다는 점이다.

이 문제의 풀이에서 꽤나 핵심적인 정보는 모눈종이의 가장자리에는 치즈가 놓이지 않는다는 것이다.

맨 바깥은 무조건 0이 입력됨을 보장받음으로써, 바깥의 0들을 dfs 등을 통해 외부라고 표시를 하면, 내부의 0과 외부의 0을 구분할 수 있다.

예를 들어 이러한 입력이 들어왔다고 하자.

단순히 위 이차원배열 자체로는 치즈 외부의 0과 내부의 0을 구분할 수 없다.

따라서 (0, 0)을 시작점으로 dfs를 통해 외부임을 표시하겠다 (내 경우는 외부를 2로 변경하였다)

탐색을 통해 외부의 0을 2로 표시함으로써, 각 치즈(1)에 대해서 2개 이상의 2와 인접한 치즈들을 0으로 변경한다.
(2로 변경할 경우 다음 치즈에 영향이 가므로 0으로 변경해 동시에 진행됨을 보장한다.)

이후 배열의 2들을 다시 0으로 되돌려놓은 후 time 값을 1 증가시킨다.

이 방법을 치즈가 모두 없어질 때까지 반복한다.

val dir = listOf(-1, 0, 1, 0, -1)

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N, M) = readLine().split(' ').map{it.toInt()}

    val map = Array(N){ readLine().split(' ').map{it.toInt()}.toTypedArray()}

    var cheeseCnt = 0
    var time = 0

    for(i in map.indices)
        for(j in map[i].indices)
            if(map[i][j] == 1)
                cheeseCnt++

    while(cheeseCnt > 0){
        changeOutside(0, 0, map)

        removeCheese(map){ cheeseCnt-- }

        time++
    }

    print(time)
}

fun changeOutside(v: Int, h: Int, map: Array<Array<Int>>){
    if(v !in map.indices || h !in map[0].indices) return

    if(map[v][h] == 0)
        map[v][h] = 2
    else return

    for(i in 0..3){
        val nextV = v + dir[i]
        val nextH = h + dir[i + 1]

        changeOutside(nextV, nextH, map)
    }
}

fun removeCheese(map: Array<Array<Int>>, remove: () -> Unit){
    for(i in 1 until map.size){
        for(j in 1 until map[i].size){
            if(map[i][j] == 1){
                var cnt = 0
                for(k in 0..3){
                    if(map[i + dir[k]][j + dir[k + 1]] == 2)
                        cnt++
                }

                if(cnt >= 2){
                    map[i][j] = 0
                    remove()
                }
            }
        }
    }

    for(i in map.indices){
        for(j in map[i].indices){
            if(map[i][j] == 2){
                map[i][j] = 0
            }
        }
    }
}

• 매번 배열을 탐색하며 치즈 개수를 세는 것은 비효율적이므로, 처음에 치즈 개수를 구한 후 치즈를 제거할 때마다 남은 개수(cheeseCnt)를 줄이는 방법을 사용하였다.

• cheeseCnt가 0이 될때까지 외부 영역(0)을 2로 변환하고 (changeOutside) 2개 이상의 2와 접한 치즈를 0으로 바꾼다.
  (바꿀 때마다 람다를 통해 cheeseCnt 감소)

• 치즈를 제거한 뒤 모든 2를 0으로 되돌린다.
  (치즈가 제거됨으로써 0과 2가 만나버리는 경우를 대비)