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

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

2933번: 미네랄

 

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

 

 

1. 설명

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

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

 

 

2. 접근방법

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

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

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

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

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

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

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

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

 

 

 

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

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

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

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

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

 

 

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

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

 

 

 

3. 소스코드

3.1. 전체 소스코드

      

      

      

    
    

      <kotlin />
    
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
}

 

전체 소스코드입니다.

 

 

3.2. throwStick

      

      

      

    
    

      <kotlin />
    
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 합니다.

 

 

3.3. findFloatingCluster

      

      

      

    
    

      <kotlin />
    
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가 끝나고 난 뒤, 미네랄 좌표 중 방문하지 않은 좌표가 있다면 공중에 떠 있는 클러스터입니다!

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

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

 

 

 

3.4. moveDownCluster

      

      

      

    
    

      <kotlin />
    
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는 아래 방향으로 가장 가까운 미네랄 까지의 거리를 찾아 내리는 메소드입니다.

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

 

 

 

4. 후기

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

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

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

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

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