[6개월 안에 백준 플래티넘 달성하기] 11. 치즈 2638 | 코틀린

 

치즈

 

문제

 

 

풀이

모눈종이 맨 가장자리에 치즈가 놓이지 않는다는 조건이 있다. 따라서 치즈 외부 공기는 모두 연결되어 있다는 것을 알 수 있다.

이를 이용하여

1. 가장자리에서 bfs를 돌면서 공기가 있는 위치에 2를 넣어준다.
2. 모눈종이 전체 배열을 돌면서 치즈가 있을 경우 치즈의 4방향 중 2의 개수를 체크해 준다. 2의 개수가 2개 이상일 경우 사라지는 치즈이므로 큐에 담아준다.
3. 큐가 빌 때 동안 사라지는 치즈의 위치에서 1번을 실행시켜 준다.
4. 치즈가 전부 사라질 때까지 2번과 3번을 반복한다.

설명은 꽤 복잡하지만 코드로 보면 금방 이해되실 겁니다.

 

import java.io.StreamTokenizer
import java.util.LinkedList

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    val N = input() // 세로
    val M = input() // 가로

    data class Pos(val y: Int, val x: Int)
    val dx = arrayOf(0,1,0,-1)
    val dy = arrayOf(-1,0,1,0)
    val arr = Array(N) { IntArray(M) {input()} }

    var result = 0

    fun bfs(startY: Int, startX: Int) {
        val queue = LinkedList<Pos> ()
        queue.add(Pos(startY,startX))
        arr[startY][startX] = 2

        while (queue.isNotEmpty()) {
            val pos = queue.poll()

            for (i in dx.indices) {
                val nextY = dy[i] + pos.y
                val nextX = dx[i] + pos.x

                if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
                    continue
                if (arr[nextY][nextX] == 0) {
                    arr[nextY][nextX] = 2
                    queue.add(Pos(nextY, nextX))
                }
            }
        }
    }


    val queue = LinkedList<Pos>()
    queue.add(Pos(0,0)) // 최초로 가장자리 공기 체크

    while (true) {

	// 주위에 공기가 있는지 체크
        while (queue.isNotEmpty()) {
            val pos = queue.poll()
            bfs(pos.y, pos.x)
        }

	// 전체 모눈종이 돌면서 사라질 치즈를 큐에 담아준다.
        var check = false
        for (i in 1 until N-1) {
            for (j in 1 until M-1) {
                if (arr[i][j] == 1) {
                    check = true
                    var count = 0
                    if (arr[i-1][j] == 2) count++
                    if (arr[i][j-1] == 2) count++
                    if (arr[i+1][j] == 2) count++
                    if (arr[i][j+1] == 2) count++
                    
                    // 녹아 없어질 치즈인 경우
                    if (count >= 2) {
                        queue.add(Pos(i,j))
                    }
                }
            }
        }
        
        if (!check) break  // 갱신이 없으면 종료
        result++
    }

    print(result)

}

 

 

위 풀이는 쉽게 이해할 수 있는 장점이 있지만 매번 모눈종이를 전체 탐색을 해야 되기 때문에 느립니다.

 

이를 해결해 주기 위해 bfs를 돌면서 동시에 방문 횟수를 체크해 주는 방법이 있습니다.

 

import java.io.StreamTokenizer
import java.util.LinkedList

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    val N = input() // 세로
    val M = input() // 가로

    data class Pos(val y: Int, val x: Int, val count: Int) // y축, x축, 시간
    val dx = arrayOf(0,1,0,-1)
    val dy = arrayOf(-1,0,1,0)
    val arr = Array(N) { IntArray(M) {input()} }
    val visited = Array(N) { IntArray(M) }   // 해당 좌표 방문 횟수

    val nextCheese = LinkedList<Pos>()

    fun bfs(startY: Int, startX: Int, count: Int) {
        val queue = LinkedList<Pos> ()
        queue.add(Pos(startY,startX, count))
        visited[startY][startX]++

        while (queue.isNotEmpty()) {
            val pos = queue.poll()

            for (i in dx.indices) {
                val nextY = dy[i] + pos.y
                val nextX = dx[i] + pos.x

                if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
                    continue
		// 치즈를 만난 경우
                if (arr[pos.y][pos.x] == 0 && arr[nextY][nextX] == 1) {
                    // 이미 사라질 치즈로 큐에 담긴 경우
                    if (visited[nextY][nextX] == 2) {
                        continue
                    } 
                    // 두 면이 공기에 닿는 치즈인 경우, 큐에 추가
                    else if (visited[nextY][nextX] == 1) {
                        visited[nextY][nextX]++
                        nextCheese.add(Pos(nextY, nextX, pos.count+1)) // 시간 갱신
                    } 
                    // 처음으로 공기에 닿는 치즈인 경우
                    else {
                        visited[nextY][nextX]++
                    }
                    continue
                }
		// 한 번도 방문하지 않은 공기인 경우
                if (arr[nextY][nextX] == 0 && visited[nextY][nextX] == 0) {
                    visited[nextY][nextX]++  // 방문체크
                    queue.add(Pos(nextY, nextX, pos.count))
                }
            }
        }
    }


    var result = 0
    bfs(0, 0, 0)

    while (nextCheese.isNotEmpty()) {
        val pos = nextCheese.poll()
        visited[pos.y][pos.x] = 1  // 공기 취급
        arr[pos.y][pos.x] = 0      // 공기 취급
        bfs(pos.y, pos.x, pos.count)
        result = pos.count

    }

    print(result)
}