[Kotlin] 백준 31863 : 내진 설계

문제 링크 : https://www.acmicpc.net/problem/31863

---

문제 해설

최초 본진 발생 후 연쇄적으로 여진이 발생합니다. 지진이 끝났을 때 무너진 건물의 개수와 무너지지 않은 건물의 개수를 구해야 합니다.

 

건물이 파괴되면 새로운 여진이 발생하고 여진까지 모두 끝나야 지진이 끝난다는 점에서 최초 진원지와 건물이 파괴된 좌표들을 저장할 덱을 선언합니다. 그리고 입력에서 진원지의 좌표를 찾아 덱에 저장해줍니다.

 

그리고 건물의 내구도가 1과 2로 나눠져있기 때문에 각 좌표에 있는 건물의 내구도를 저장할 2차원 배열을 선언해줍니다.

val epicenter = ArrayDeque<Pair<Int, Int>>()
val durability = Array(n) { IntArray(m) }
var buildingCount = 0
var destroiedCount = 0
for (i in 0..<n) {
    for (j in 0..<m) {
        if (map[i][j] == '@') epicenter.add(i to j)
        durability[i][j] = when (map[i][j]) {
            '#' -> 2.also { buildingCount++ }
            '*' -> 1.also { buildingCount++ }
            else -> 0
        }
    }
}

진원지에서 상하좌우로 지진이 뻗어나가므로 뻗어나갈 방향도 배열로 선언해줍니다.

val dr = intArrayOf(-1, 1, 0, 0)
val dc = intArrayOf(0, 0, -1, 1)

이제 본격적으로 지진이 발생하는 상황을 구현해줍니다.

 

최초의 진원지에서 발생하는 본진은 상하좌우 2칸씩, 이후에 건물이 무너져서 발생하는 여진은 상하좌우 1칸씩 뻗어나가는 점을 제외하면 지진이 발생했을 때의 로직은 다르지 않습니다. 그래서 지진이 뻗어나갈 칸 수를 받아서 지진이 발생했을 때의 동작을 수행할 함수 하나를 선언해서 사용했습니다.

fun earthquake(r: Int, c: Int, count: Int) {
    for (i in 0..3) {
        var nr = r
        var nc = c
        for (j in 1..count) {
            nr += dr[i]
            nc += dc[i]
            if (nr !in 0..<n || nc !in 0..<m || map[nr][nc] == '|') break
            if (durability[nr][nc] == 0) continue
            if (--durability[nr][nc] == 0) {
                destroiedCount++
                buildingCount--
                epicenter.add(nr to nc)
            }
        }
    }
}

count의 값만큼 지진이 뻗어나게 하기 위해 반복문을 추가로 작성했습니다.

 

지진이 뻗어나가다가 지도 밖을 벗어나거나 방파제를 만나면 해당 방향으로의 이동을 중단합니다. 그리고 건물의 내구도가 0인 칸(= 건물이 파괴되었거나 처음부터 건물이 없었던 칸)을 만나면 다음 칸으로 넘어갑니다.

 

이제 건물을 만나면 건물의 내구도를 1 감소시켜줍니다. 이렇게 감소된 건물의 내구도가 0이 되면 건물이 파괴되기 때문에 건물이 파괴된 현재 좌표를 새로운 진원지에 추가해줍니다. 문제에서 구해야 할 값은 파괴된 건물의 개수와 남은 건물의 개수이므로 이 값들도 계산해줍니다.

 

함수 작성이 끝났으니 이제 시뮬레이션을 하기만 하면 됩니다. 최초 진원지에 한해서 지진이 2칸을 뻗어나가도록 하고 그 이후에는 진원지가 남아있는동안(= 덱이 비어있지 않으면 반복해서) 지진이 1칸을 뻗어나가도록 하면 됩니다.

val (startR, startC) = epicenter.removeFirst()
earthquake(startR, startC, 2)
while (epicenter.isNotEmpty()) {
    val (r, c) = epicenter.removeFirst()
    earthquake(r, c, 1)
}

Code

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(' ').map { it.toInt() }
    val map = Array(n) { readLine().toCharArray() }
    val epicenter = ArrayDeque<Pair<Int, Int>>()
    val durability = Array(n) { IntArray(m) }
    var buildingCount = 0
    var destroiedCount = 0
    for (i in 0..<n) {
        for (j in 0..<m) {
            if (map[i][j] == '@') epicenter.add(i to j)
            durability[i][j] = when (map[i][j]) {
                '#' -> 2.also { buildingCount++ }
                '*' -> 1.also { buildingCount++ }
                else -> 0
            }
        }
    }
    val dr = intArrayOf(-1, 1, 0, 0)
    val dc = intArrayOf(0, 0, -1, 1)
    fun earthquake(r: Int, c: Int, count: Int) {
        for (i in 0..3) {
            var nr = r
            var nc = c
            for (j in 1..count) {
                nr += dr[i]
                nc += dc[i]
                if (nr !in 0..<n || nc !in 0..<m || map[nr][nc] == '|') break
                if (durability[nr][nc] == 0) continue
                if (--durability[nr][nc] == 0) {
                    destroiedCount++
                    buildingCount--
                    epicenter.add(nr to nc)
                }
            }
        }
    }
    val (startR, startC) = epicenter.removeFirst()
    earthquake(startR, startC, 2)
    while (epicenter.isNotEmpty()) {
        val (r, c) = epicenter.removeFirst()
        earthquake(r, c, 1)
    }
    println("$destroiedCount $buildingCount")
}