백준 - 18500번: 미네랄(Kotlin)

제한사항

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

느낀 점

아이디어 생각하는데 은근 시간을 뺏겼고, 구현하는 데에도 시간을 많이 뺏겼다.

요즘 느끼는 건데, 알고리즘에 큰 틀만 짜고 바로 코드 작성에 들어가면 이번처럼 코드가 꼬이거나 망가진다.

가독성이 떨어지고, 방향을 반대로 처리하거나, 불필요한 코드가 반복된다.

문제 자체가 난이도가 높아서 어려운 것도 있었지만, 처음 시작할 때 큰 틀만이 아니라 디테일을 생각하고 갔어야 했다.

다음에는 반성하고 그렇게 풀자.

그래도 예전에 브론즈에서 쩔쩔 매던 시절 생각하면 많이 발전했다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import kotlin.math.absoluteValue

// 위부터 시계방향
private val dy = intArrayOf(1, 0, -1, 0)
private val dx = intArrayOf(0, 1, 0, -1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (r, c) = readLine().split(" ").map { it.toInt() }
    var map = Array(r) { readLine().toCharArray() }
    reverseArray(map)

    var stickCnt = readLine().toInt()
    val stickThrownHeights = readLine().split(" ").map { it.toInt() - 1 }.toIntArray()

    for (stickIdx in stickThrownHeights.indices) {
        val height = stickThrownHeights[stickIdx]
        val thrownStickCount = stickIdx + 1
        val direction = if (thrownStickCount.rem(2) == 1) {
            Direction.LEFT
        } else {
            Direction.RIGHT
        }

        val crashingCol = throwStick(height, direction, map)
        // 던진 막대가 아무 것도 붙이지 않았으면 다음 막대기로 넘어간다.
        if (crashingCol == Int.MAX_VALUE) {
            continue
        }
        
        // 던진 부분 주변 클러스터 확인
        val crashingAroundMineral = LinkedList<Pair<Int, Int>>()
        for (directionIdx in 0..3) {
            val nextY = height + dy[directionIdx]
            val nextX = crashingCol + dx[directionIdx]
            if (nextY !in map.indices || nextX !in map[0].indices) {
                continue
            }

            // 막대기가 부딪힌 곳 주변에 미네랄이 있으면 부셔졌는지 확인하기 위해 리스트에 넣어준다.
            if (map[nextY][nextX] == 'x') {
                crashingAroundMineral.push(nextY to nextX)
            }
        }

        // 막대기가 부딪힌 곳 주변에 미네랄이 없으면, 미네랄이 떨어질 일이 없으므로 다음 막대기로 넘어간다.
        if (crashingAroundMineral.first == null) {
            continue
        }

        // BFS를 통해, 클러스터를 구하는 과정
        val visited = Array(r) { BooleanArray(c) { false } }
        val clusterList = LinkedList<LinkedList<Pair<Int, Int>>>()
        for (mineralPosition in crashingAroundMineral) {
            if (visited[mineralPosition.first][mineralPosition.second]) {
                continue
            }

            val queue = LinkedList<Pair<Int, Int>>()
            queue.offer(mineralPosition)
            visited[mineralPosition.first][mineralPosition.second] = true
            // 클러스터의 미네랄 좌표들을 저장할 리스트
            val cluster = LinkedList<Pair<Int, Int>>()
            cluster.push(mineralPosition)

            while (queue.isNotEmpty()) {
                val searchedMineral = queue.poll()

                for (directionIdx in 0..3) {
                    val nextY = searchedMineral.first + dy[directionIdx]
                    val nextX = searchedMineral.second + dx[directionIdx]

                    if (nextY !in map.indices || nextX !in map[0].indices || visited[nextY][nextX]) {
                        continue
                    }
                    visited[nextY][nextX] = true

                    if (map[nextY][nextX] != 'x') {
                        continue
                    }

                    // 탐색하지 않았으므로 BFS를 위해 queue에 넣는다.
                    queue.offer(nextY to nextX)
                    // BFS를 통해 인접한 미네랄을 구한 것이므로 같은 클러스터에 속한다.
                    // 따라서, 클러스터에 넣어준다.
                    cluster.push(nextY to nextX)
                }
            }

            // 클러스터를 구했으므로 클러스터 리스트에 넣어준다.
            clusterList.add(cluster)
        }

        // 해당 클러스트가 내려갈 수 있는지 확인
        for (cluster in clusterList) {
            // 내려 갈 때, 미네랄을 만나면 클러스터에 속한 미네랄인지 다른 클러스터에 속한 미네랄인지 확인이 불가능하다.
            // 따라서, 현재 클러스터가 제거된 맵을 만든다. 이렇게하면 맵에서 만난 미네랄은 모두 자신이 아닌 다른 클러스터에 속한 미네랄이다.
            val clusterRemovedMap = Array(r) { CharArray(c) }
            copyArray(map, clusterRemovedMap)
            cluster.forEach {
                clusterRemovedMap[it.first][it.second] = '.'
            }

            // 밑으로 이동 가능한 횟수를 구한다.
            val movement = getMaximumMovement(cluster, clusterRemovedMap)
            // 0이면 이동 필요 없음. 다음 클러스터를 확인한다.
            if (movement == 0) {
                continue
            }

            // 클러스터가 하나라도 움직이면, 다른 클러스터는 체크할 필요가 없다.
            // 문제 조건에서 하나만 움직인다고 조건을 줬으니까.
            var isClusterMoved: Boolean = false
            for (pair in cluster) {
                clusterRemovedMap[pair.first - movement][pair.second] = 'x'
                isClusterMoved = true
            }

            // 클러스트는 하나만 움직일 수 있으므로, 움직인 순간 다른 클러스터 체크할 필요가 없음.
            if (isClusterMoved) {
                map = clusterRemovedMap
                break
            }
        }
    }

    reverseArray(map)
    map.forEach {
        println(it)
    }
}

fun getMaximumMovement(cluster: LinkedList<Pair<Int, Int>>, clusterRemovedMap: Array<CharArray>): Int {
    var movement = 1
    while (movement.absoluteValue <= clusterRemovedMap.size) {
        var isLimitDownMovement = false
        for (mineral in cluster) {
            val nextY = mineral.first - movement
            val nextX = mineral.second
            // 맵 밖이거나, 밑에 미네랄이 있으면 더 못내려감.
            if (nextY !in clusterRemovedMap.indices || nextX !in clusterRemovedMap[0].indices || clusterRemovedMap[nextY][nextX] == 'x') {
                isLimitDownMovement = true
                break
            }
        }

        if (!isLimitDownMovement) {
            movement++
            continue
        }
        return --movement
    }

    return -1
}

enum class Direction {
    LEFT, RIGHT
}

fun throwStick(height: Int, startDirection: Direction, map: Array<CharArray>): Int {
    if (startDirection == Direction.LEFT) {
        for (col in map[0].indices) {
            if (map[height][col] == 'x') {
                map[height][col] = '.'
                return col
            }
        }
    } else {
        for (col in map[0].size - 1 downTo 0) {
            if (map[height][col] == 'x') {
                map[height][col] = '.'
                return col
            }
        }
    }

    return Int.MAX_VALUE
}

fun copyArray(original: Array<CharArray>, destination: Array<CharArray>) {
    for (r in original.indices) {
        for (c in original[0].indices) {
            destination[r][c] = original[r][c]
        }
    }
}

fun reverseArray(array: Array<CharArray>) {
    for (col in array[0].indices) {
        for (row in 0..<(array.size/2)) {
            val temp = array[row][col]
            array[row][col] = array[array.size - row - 1][col]
            array[array.size - row - 1][col] = temp
        }
    }
}