백준 [2638] kotlin

[문제]

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

2638번: 치즈

[풀이]

이 문제의 핵심은 다음과 같다.

1. 바깥과 닿아있는 부분만 외부 공기이다. 치즈로 둘러쌓인 내부의 공기는 외부 공기가 아니다.
2. 외부 공기와 최소 2면이 닿는 치즈는 한 시간 후에 녹는다.

BFS 과정은 다음과 같다.

이동할 배열을 저장해두는 deque를 생성한다.

가장 먼저, 방문한 곳을 기록해두는 visit이라는 배열을 생성한다. 방문한 곳은 -1로 저장을 하고, 치즈인곳은 접한 횟수를 체크해야하기 때문에 치즈인 곳을 찾을 때마다 기존 값에 +1을 해준다.

 

외각 공기로 이동을 하면서, 상하좌우를 체크를 한다.

 

이 때 두 가지 경우로 나뉜다.

1. 치즈인 경우

치즈인 경우에는 visit배열에 +1을 해준다.

2. 공기인 경우

이미 방문한 공기인지 체크하기 위해 visit가 -1이 아니면, 방문을 한 적이 없는 경우이므로 -1로 저장을 하고 deque에 추가를 한다.

 

BFS가 끝나면, visit 배열을 탐색하면서 2이상인 위치의 cheese를 0으로 바꾸어 준다.

 

위의 BFS과정을 모든 치즈가 녹을때까지 반복한다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.Deque
import java.util.LinkedList

var N = 0
var M = 0
lateinit var cheese : ArrayList<ArrayList<Int>>
var dx = listOf(0,0,1,-1)
var dy = listOf(1,-1,0,0)
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    val tmp = br.readLine().split(" ").map { it.toInt() }
    N = tmp[0]
    M = tmp[1]

    cheese = arrayListOf()
    repeat(N) {cheese.add(ArrayList(br.readLine().split(" ").map { it.toInt() })) }

    var ans = 0
    /* 외각 찾기 */
    val k = findZero()
    while (true)
    {
        if(bfs(k.first,k.second)) ans++
        else break
    }
    bw.write(ans.toString())
    bw.flush()
    bw.close()
}
fun findZero() : Pair<Int, Int>
{
    for (i in 0 until N)
    {
        if(cheese[i][0]==1) return Pair(i,0)
        if(cheese[i][M-1]==1) return Pair(i,M-i)
    }
    for (i in 0 until M)
    {
        if(cheese[0][i]==1) return Pair(0,i)
        if(cheese[N-1][i]==1) return Pair(N-1,i)
    }
    return Pair(0,0)
}

fun bfs(x : Int, y : Int) : Boolean
{
    var q : Deque<Pair<Int,Int>> = LinkedList()
    var visited = Array(N, {IntArray(M,{0})})
    q.add(Pair(x,y))
    while (q.isNotEmpty())
    {
        val pq = q.removeFirst()
        repeat(4)
        {
            i ->
            var nx = pq.first + dx[i]
            var ny = pq.second + dy[i]
            if(nx in 0 until N && ny in 0 until M)
            {
                /* 치즈가 있는 곳인 경우 */
                if(cheese[nx][ny] == 1)
                {
                    visited[nx][ny]++
                }
                /* 치즈가 없는 곳인 경우 */
                else
                {
                    /* 방문한 치즈인지 체크 */
                    if(visited[nx][ny] != -1) {
                        visited[nx][ny] = -1
                        q.add(Pair(nx,ny))
                    }
                }
            }
        }
    }
    var check = false
    for(i in 0 until N)
    {
        for(j in 0 until M)
        {
            if(visited[i][j] >= 2)
            {
                cheese[i][j] = 0
                check = true
            }
        }
    }
    return check
}