[백준 2638번] [Kotlin] 치즈

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

2638번: 치즈

 

난이도 : 골드 3
태그 : 구현, 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색, 시뮬레이션

 

 

설명

외부 공기와 접촉하는 칸이 두 곳 이상이면 치즈가 녹습니다.

이때, 모든 치즈가 녹으려면 얼마만큼의 시간이 필요한지 구하는 문제입니다.

 

DFS, BFS 중 어느것을 사용해도 무방하나, 저는 DFS를 사용하여 풀이하였기에,

본 포스팅에선 DFS를 사용한 접근법과 풀이를 서술하도록 하겠습니다.

 

 

접근방법

1. 일반적으로 방문여부를 체크하는 Boolean 타입의 visited 배열 대신, 방문 횟수를 체크할 것이기에 Int 타입의 visited 배열로 방문 횟수를 체크합니다.
2. 방문한 칸이 치즈일 경우 visited 배열을 +1 만큼 증가시키고, 치즈가 아닐 경우 바로 2로 지정합니다
3. visited가 2 이상인 칸은 map을 0으로 변경(치즈 없는 칸)합니다. 또한, visited 배열도 다시 0으로 초기화 시켜주고, 시간이 얼마나 흘렀는지를 저장하는 hour도 +1씩 합니다.
4. 모든 칸이 0이 될 때까지 위 과정을 반복합니다

 

 

 

소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

var n = 0
var m = 0
var hour = 0
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
lateinit var map: Array<Array<Int>>
lateinit var visited: Array<Array<Int>>

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val nm = br.readLine().split(" ").map { it.toInt() }
    n = nm[0]
    m = nm[1]

    map = Array(n) { Array(m) { 0 } }
    visited = Array(n) { Array(m) { 0 } }

    // 맵 정보 입력
    repeat(n) { x ->
        val st = StringTokenizer(br.readLine())
        repeat(m) { y ->
            map[x][y] = st.nextToken().toInt()
        }
    }

    while (true) {
        var sum = 0
        map.forEach { it.forEach { sum += it } }
        if (sum == 0) break // 맵 모두 치즈가 없으면 break

        dfs(0, 0) // 맵 가장자리는 치즈가 없음

        // 방문횟수가 2 이상인 경우 (치즈 있는 칸을 두 번 이상 접근하거나 치즈가 없는 칸일 경우) 0 으로 변경
        // visited 도 다시 0으로
        for (i in 0 until n) {
            for (j in 0 until m) {
                if (visited[i][j] >= 2) map[i][j] = 0
                visited[i][j] = 0
            }
        }

        hour++
    }

    println(hour)
}


fun dfs(x: Int, y: Int) {
    // 치즈가 있을경우 방문횟수 +1
    if (map[x][y] == 1) {
        visited[x][y]++
        return
    }
    // 치즈가 아닐경우 방문횟수 2로 고정
    visited[x][y] = 2


    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        // 범위를 벗어나는지 검사 / 방문횟수가 2회 이상인지 검사
        if (nx !in 0 until n || ny !in 0 until m || visited[nx][ny] >= 2) continue

        dfs(nx, ny)
    }
}

 

전체 소스코드 입니다.

 

무한반복 while문을 돌면서, 모든 칸이 0일 경우 반복문을 break 합니다.

맵의 가장자리 부분은 치즈가 없다고 문제에 명시되어 있으므로,

모든 좌표에 dfs를 수행할 필요 없이 0, 0 좌표에(혹은 가장자리 아무데나) 한번만 돌리면 됩니다.

 

 

 

후기

dfs/bfs를 사용해 방문횟수를 체크해가며 탐색을 하는,

풀면서 꽤 재밌었던 문제였습니다.

 

기존까지 블로그 코딩테스트 풀이 형식을

전체 소스코드를 올리고, 부분별로 설명을 하는 식이였는데

가독성이 그닥 좋지 않은 것 같아 소스코드에 주석을 첨부하는 형식으로 변경하였습니다.

좀 더 깔끔해진것 같네요.