요새 백준 열심히 풀고 있는데 정리및 복습하는 겸해서 풀이도 올리겠다.

단순한 그래프 시뮬레이션 문제인데 생각보다 고려해야 할 요소가 많아서 제법 고민을 많이 했던 문제이다.

문제 요약

문제는 동굴 안에 미네랄이 있고, 창영이와 상근이가 막대기를 던져서 미네랄을 파괴하는 시뮬레이션 게임이다. 막대기를 던지면 미네랄이 파괴되고, 파괴된 이후에 떠 있는 미네랄 클러스터가 있다면 중력의 영향으로 아래로 떨어지게 된다. 이 과정에서 분리된 클러스터가 다른 클러스터나 바닥에 안착할 때까지 떨어지는 것을 정확하게 계산해야 하는 문제이다.

문제 풀이

내가 문제를 보고 떠올린 문제 접근은 창에 맞아 부셔진 미네랄에 인접한 부분에서 4방향으로 dfs를 진행해 바닥과 접해 있지 않은 클러스터에 대해서만 이동을 진행하는 것이였다

일단 구현 자체는 어렵지 않았다

창을 던지는 순서에 따른 방향은 인덱스 % 2 를 통해 진행하였고

바닥과 인접하지 않은 부분의 클러스터가 존재할때, 그 부분에 대해서 바닥 또는 미네랄과 부딪히기 직전 이동거리만큼 이동시켜주면 된다.

오류

나는 다른 부분 구현은 어렵지 않았지만 논리적으로 실수를 한 부분이 있는데

1. 떨어지는 거리

떨어지는 거리를 계산할 때 좀 더 효율적으로 하고 싶어서 해당 클러스터의 각 열 중 가장 바닥과 근접한 부분에 대해서만 바닥 및 미네랄과의 거리를 계산하였다.

하지만 이 부분은 오류가 있는게 아래쪽 클러스터보다 중간의 클러스터에 먼저 닿을 수 있다는 것이다

2. 이동 처리

나는 초기에 구현할 때 이동하기 전 기존 위치는 빈 공간으로 만들고 이동하는 위치는 x로 바꿔 주었는데 이 부분에서 오류가 났다

즉 기존 위치의 미네랄을 제거하기 전에 새 위치에 미네랄을 추가하는 잘못된 접근을 했던 것이다.
이렇게 하면 이동하는 과정에서 클러스터의 일부가 다른 부분에 의해 덮어쓰여질 수 있다. 즉 이동했던 부분이 기존 위치라서 이동했던 위치가 또 제거 되는 불상사가 일어날 수 있다는 것이다.
올바른 접근은 실제로 이동시키기 전에 원래 위치의 미네랄을 제거해야 한다.

아래 반례가 틀린다면 이 부분을 고려해보자

9 8
........
...xxx..
.xxx....
.x.x.xxx
.x.x...x
.x.xxx.x
.x.....x
.x.....x
.xxx...x
1
7

답)
........
........
...xxx..
.xxx.xxx
.x.x...x
.x.x...x
.x.xxx.x
.x.....x
.xxx...x

코드

코드가 좀 길다

data class Cluster(val parts: ArrayList<Part> = arrayListOf())
data class Part(val x: Int, val y: Int)

fun main() {
    val br = System.`in`.bufferedReader()
    val (r, c) = br.readLine().split(" ").map { it.toInt() }
    val board = Array(r) { br.readLine().toCharArray() }
    val n = br.readLine().toInt()
    val hs = br.readLine().split(" ").map { it.toInt() }
    
    val moveX = arrayOf(0, 0, -1, 1)
    val moveY = arrayOf(1, -1, 0, 0)

    // height 만큼 cluster 이동
    fun moveCluster(cluster: Cluster, height: Int) {
        // 이동 전에 모든 위치를 '.'으로 변경
        cluster.parts.forEach { (x, y) ->
            board[x][y] = '.'
        }

        // 이동 후에 미네랄 위치 업데이트
        cluster.parts.forEach { part ->
            board[part.x + height][part.y] = 'x'
        }
    }

    //떨어질 수 있는 클러스터 height구하기
    fun downCluster(cluster: Cluster) {

        var height = 0

        // 초기포지션
        val firstPosition = Array(r) { BooleanArray(c) }

        cluster.parts.forEach {
            firstPosition[it.x][it.y] = true
        }

        while (true) {
            height++
            val result = cluster.parts.all {
                val x = it.x + height
                val y = it.y
                x in board.indices && (board[x][y] == '.' || firstPosition[x][y])
            }
            if (!result) break
        }
        height--
        // 한칸이라도 떨어질 수 있다면
        if (height >= 1) {
            moveCluster(cluster, height)
        }
    }

    // 떨어지는 클러스터 찾기
    fun findDownCluster(
        visited: Array<BooleanArray>,
        startX: Int,
        startY: Int,
    ): Pair<Boolean, Cluster> {
        var flag = true
        val cluster = Cluster()

        fun dfs(visited: Array<BooleanArray>, x: Int, y: Int) {
            visited[x][y] = true
            cluster.parts.add(Part(x, y))
            // 바닥에 닿아있다면 안 떨어짐
            if (x == r - 1) flag = false
            for (i in 0 until 4) {
                val nx = x + moveX[i]
                val ny = y + moveY[i]
                if (nx in board.indices && ny in board[0].indices && !visited[nx][ny] && board[nx][ny] == 'x') {
                    dfs(visited, nx, ny)
                }
            }
        }

        dfs(visited, startX, startY)
        return Pair(flag, cluster)
    }

    // 해당 옆에서 던지는 방향에서 가장 근접한 x 찾고 부수기
    for (i in hs.indices) {
        // 왼쪽에서 오른쪽
        val height = r - hs[i]
        val idx = if (i % 2 == 0) {
            board[height].indexOfFirst { it == 'x' }
        } else {
            // 오른쪽에서 왼쪽
            board[height].indexOfLast { it == 'x' }
        }

        // 미네랄이 창에 의해 안깨지면 continue
        if (idx != -1) board[height][idx] = '.'
        else continue

        // 깨졌다면 그 주위 탐색으로 down 클러스터 찾기
        val visited = Array(r) { BooleanArray(c) }
        var downCluster: Cluster? = null
        for (j in 0 until 4) {
            val nx = height + moveX[j]
            val ny = idx + moveY[j]
            if (nx in board.indices && ny in board[0].indices && !visited[nx][ny] && board[nx][ny] == 'x') {
                val result = findDownCluster(visited, nx, ny)
                if (result.first) {
                    downCluster = result.second
                }
            }
        }

        // 떨어지는 클러스터가 있다
        if (downCluster != null) downCluster(downCluster)
    }


    val sb = StringBuilder()
    board.forEach {
        sb.append(it.joinToString("")).append("\n")
    }
    print(sb.toString().trimEnd())
}

배운점

이런 문제에서 한 단계씩 구현할때 논리적인 오류가 안 발생하게 하는 능력을 키워야겠다...