[백준 2573번] [Kotlin] 빙산

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

2573번: 빙산

난이도 : 골드 4
태그 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

설명

얼음을 녹이면서 덩어리가 두개가 되는 시점을 찾는 문제입니다.

얼음을 녹이는 구현 부분에 약간의 시뮬레이션 요소가 들어갔다고 볼 수 있을 것 같네요.

얼음이 몇 덩어리인지 확인하는 부분은 DFS / BFS 를 사용할 수 있을 것 같은데,

저는 DFS를 사용해 풀이하였습니다.

 

 

 

접근 방법

1. 얼음을 녹인다

얼음이 녹음으로써 바로 옆 칸의 결과에 영향을 줄 수 있기 때문에 맵을 하나 더 만든 후 결과값을 적용시켜야 합니다.

2. 모든 정점에서 DFS를 수행하며 얼음 덩어리가 총 몇개 있는지 확인한다.

3 - 1. 얼음 덩어리가 1개라면 1번 과정으로 돌아간다.

3 - 2. 얼음 덩어리가 2개 이상이라면 결과값을 출력하고 종료한다.

3 - 3. 얼음 덩어리가 0개라면 2개 이상으로 쪼개지기 전에 다 녹은 것이므로, 0을 출력하고 종료한다.

 

 

 

소스코드

import java.util.StringTokenizer

var n = 0
var m = 0

val dx = intArrayOf(0, 0, -1, 1)
val dy = intArrayOf(-1, 1, 0, 0)

lateinit var visited: Array<Array<Boolean>>
lateinit var map: Array<Array<Int>>
var iceGroupCnt = 0

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

    map = Array(n) {
        val st = StringTokenizer(readLine())
        Array(m) { st.nextToken().toInt() }
    }

    var year = 0

    while (true) {
        year++
        melt()
        visited = Array(n) { Array(m) { false } }
        iceGroupCnt = 0

        for (i in 0 until n) {
            for (j in 0 until m) {
                if (dfs(i, j)) iceGroupCnt++
                if (iceGroupCnt >= 2) {
                    println(year)
                    return
                }
            }
        }

        if (iceGroupCnt == 0) {
            println(0)
            return
        }
    }
}

fun dfs(x: Int, y: Int): Boolean {
    if (map[x][y] == 0 || visited[x][y]) return false
    visited[x][y] = true

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

        if (nx !in 0 until n || ny !in 0 until m || visited[nx][ny] || map[nx][ny] == 0) continue
        dfs(nx, ny)
    }

    return true
}

fun melt() {
    val meltMap = Array(n) { Array(m) { 0 } }
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (map[i][j] == 0) continue

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

                if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] != 0) continue
                meltMap[i][j]++
            }
        }
    }

    for (i in 0 until n) {
        for (j in 0 until m) {
            map[i][j] -= meltMap[i][j]
            if (map[i][j] < 0) map[i][j] = 0
        }
    }
}

 

 

 

 

후기

꽤 비슷한 유형을 여러 번 풀어봤던 탓에,

금방 풀 수 있었 던 것 같네요.

DFS는 역시 최고야. 짜릿해.