[백준 2933번] [Kotlin] 미네랄

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

2933번: 미네랄

 

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

 

 

설명

창영이와 상근이가 차례로 막대기를 던져 미네랄을 파괴하는 문제입니다.

막대기는 수평으로만 날아가며, 미네랄이 파괴되면 해당 미네랄 클러스터를 내립니다.

 

 

접근방법

1. 막대기를 던진다. 첫 시작은 왼쪽 -> 오른쪽 이며, 번갈아가며 던진다

2. 막대기가 미네랄을 파괴했을 경우, 공중에 떠 있는 클러스터를 찾는다.

2-1. 1층의 모든 좌표를 큐에 미리 넣고, BFS를 돌린다.

2-2. BFS가 끝난 뒤 방문하지 않았으면서 미네랄이 있는 좌표가 있다면, 공중에 떠 있는 미네랄(클러스터)다!

3. 떠 있는 클러스터가 있을 경우 해당 클러스터를 내린다.

3-1. 해당 클러스터를 '*'등 다른 문자로 바꾼 뒤, 클러스터의 각 미네랄로부터 밑으로 가장 가까운 미네랄까지의 거리를 구한다.

3-2. 해당 거리만큼 클러스터를 내린다.

4. 위 과정을 k번 반복한다. 

 

 

 

떠 있는 클러스터를 찾았을 경우, 해당 클러스터를 * 등 다른 문자로 바꾸는 이유는,

클러스터의 모든 미네랄에 대해 밑으로 가장 가까운 미네랄을 찾을 경우, 같은 클러스터의 미네랄을 찾는 경우가 발생했기 때문입니다..!

위 그림에서 해당 클러스터는 3만큼 내릴 수 있지만,

모든 미네랄에서 밑으로 가장 미네랄을 찾았을 경우, 1만큼 밖에 내리지 못하였기에,

같은 클러스터 내 미네랄은 예외처리를 해주기 위해 * 등 다른 문자로 바꿔줬습니다.

 

 

* 흔히 배열에서 가장 밑의 칸의 좌표는 n이지만, 해당 문제에서는 가장 밑의 칸 부터 1층으로 세기 때문에,

맵을 입력받은 뒤 reverse 해줬습니다.

 

 

 

소스코드

전체 소스코드

import java.util.ArrayList
import java.util.StringTokenizer

data class Node(val x: Int, val y: Int)

lateinit var map: List<CharArray>
val dx = intArrayOf(1, -1, 0, 0)
val dy = intArrayOf(0, 0, 1, -1)
var n = 0
var m = 0

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

    map = Array(n) { readLine().toCharArray() }.reversed()

    val k = readLine().toInt()
    val st = StringTokenizer(readLine())

    repeat(k) {
        val x = st.nextToken().toInt() - 1
        val isLTR = it % 2 == 0 // LTR -> Left To Right

        val isHitMineral = throwStick(x, isLTR)

        if (isHitMineral) {
            val foundCluster = findFloatingCluster()
            if (foundCluster.isEmpty()) return@repeat

            moveDownCluster(foundCluster)
        }
    }

    val sb = StringBuilder()
    map.reversed().forEach { sb.appendLine(it) }
    print(sb.toString())
}

fun moveDownCluster(foundCluster: ArrayList<Node>) {
    foundCluster.forEach { (x, y) -> map[x][y] = '*' } // 떨어질 클러스터는 '*'로 표시

    var maxDownDistance = Int.MAX_VALUE

    foundCluster.forEach { (x, y) ->
        var downDistance = 0

        for (height in x - 1 downTo 0) {
            if (map[height][y] == 'x') break
            downDistance++
        }

        maxDownDistance = minOf(maxDownDistance, downDistance)
    }

    foundCluster.forEach { (x, y) ->
        map[x][y] = '.'
        map[x - maxDownDistance][y] = 'x'
    }
}

fun findFloatingCluster(): ArrayList<Node> {
    val visited = Array(n) { BooleanArray(m) }
    visited[0].fill(true)

    val queue = ArrayDeque<Node>()
    for (i in 0..<m) {
        if (map[0][i] == 'x') {
            queue.add(Node(0, i))
        }
    }

    while (queue.isNotEmpty()) {
        val cur = queue.removeFirst()

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

            if (nx !in 0..<n || ny !in 0..<m || visited[nx][ny] || map[nx][ny] != 'x') continue

            visited[nx][ny] = true
            queue.add(Node(nx, ny))
        }
    }

    val floatingCluster = ArrayList<Node>()
    for (x in 1..<n) {
        for (y in 0..<m) {
            if (map[x][y] == 'x' && !visited[x][y]) {
                floatingCluster.add(Node(x, y))
            }
        }
    }

    return floatingCluster
}

fun throwStick(x: Int, isLTR: Boolean): Boolean {
    val range = if (isLTR) 0..<m else m - 1 downTo 0

    for (y in range) {
        if (map[x][y] == 'x') {
            map[x][y] = '.'
            return true
        }
    }
    return false
}

 

전체 소스코드입니다.

 

 

throwStick

fun throwStick(x: Int, isLTR: Boolean): Boolean {
    val range = if (isLTR) 0..<m else m - 1 downTo 0

    for (y in range) {
        if (map[x][y] == 'x') {
            map[x][y] = '.'
            return true
        }
    }
    return false
}

 

막대기를 던져 클러스터를 파괴하는 작업을 하는 메소드입니다.

막대기를 던지는 위치 x와 isLTR(Left To Right)를 매개변수로 받아

해당 높이에 있는 미네랄을 부숩니다.

단, 미네랄은 한 개만 부술 수 있으므로, 미네랄을 파괴하는 즉시 return 합니다.

 

 

findFloatingCluster

fun findFloatingCluster(): ArrayList<Node> {
    val visited = Array(n) { BooleanArray(m) }
    visited[0].fill(true)

    val queue = ArrayDeque<Node>()
    for (i in 0..<m) {
        if (map[0][i] == 'x') {
            queue.add(Node(0, i))
        }
    }

    while (queue.isNotEmpty()) {
        val cur = queue.removeFirst()

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

            if (nx !in 0..<n || ny !in 0..<m || visited[nx][ny] || map[nx][ny] != 'x') continue

            visited[nx][ny] = true
            queue.add(Node(nx, ny))
        }
    }

    val floatingCluster = ArrayList<Node>()
    for (x in 1..<n) {
        for (y in 0..<m) {
            if (map[x][y] == 'x' && !visited[x][y]) {
                floatingCluster.add(Node(x, y))
            }
        }
    }

    return floatingCluster
}

 

가장 밑의 모든 좌표를 큐에 넣고 BFS를 돌렸습니다.

BFS가 끝나고 난 뒤, 미네랄 좌표 중 방문하지 않은 좌표가 있다면 공중에 떠 있는 클러스터입니다!

막대기를 한 번 던졌을 때, 생성될 수 있는 클러스터는 무조건 한 개 이므로,

여러개의 클러스터가 떠 있는 경우는 고려하지 않아도 됩니다.

 

 

 

moveDownCluster

fun moveDownCluster(foundCluster: ArrayList<Node>) {
    foundCluster.forEach { (x, y) -> map[x][y] = '*' } // 떨어질 클러스터는 '*'로 표시

    var maxDownDistance = Int.MAX_VALUE

    foundCluster.forEach { (x, y) ->
        var downDistance = 0

        for (height in x - 1 downTo 0) {
            if (map[height][y] == 'x') break
            downDistance++
        }

        maxDownDistance = minOf(maxDownDistance, downDistance)
    }

    foundCluster.forEach { (x, y) ->
        map[x][y] = '.'
        map[x - maxDownDistance][y] = 'x'
    }
}

 

moveDownCluster는 아래 방향으로 가장 가까운 미네랄 까지의 거리를 찾아 내리는 메소드입니다.

앞서 말한 것 처럼, 같은 미네랄을 인식할 수도 있어 공중에 떠 있는 미네랄을 *로 바꿔줬습니다.

 

 

 

후기

문제 내용과 접근 방법 자체는 쉬우나,

구현 과정이 다소 만만치 않았던 문제였던 것 같습니다.

사실 코테를 할 때엔 main 함수에 모든 코드를 다 넣곤 했는데,

메소드가 하나의 역할만 할 수 있도록 메소드를 나누는 연습을 하고 있습니다.

확실이 main에 다 넣는 것 보다는 읽기 쉬운 코드가 된 것 같네요.