백준 - 2933 미네랄 (코틀린)

[문제]

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

2933번: 미네랄

[풀이]

bfs와 구현, 시뮬레이션 문제이다. 막대를 던진 높이를 배열에 저장하고 해당 인덱스를 이용해서 왼쪽에서 던질지 오른쪽에서 던질지 정한다. 던지면서 'x'를 만난다면 지우고 '.'로 바꿔준다. 그리고 해당 좌표의 위,아래,좌,우 좌표가 'x' 라면 해당 좌표에서 시작하는 미네랄이 바닥과 연결되어 있는지 아닌지 구한다. 연결되어 있다면 이동을 시킬 필요가 없으니 넘어가고 연결되어 있지 않다면 해당하는 미네랄을 움직여야 하는데 해당 미네랄의 가장 낮은 y좌표와 큰 y좌표를 구하고 해당 구간에서 해당 미네랄과 바닥이나 바닥이 아닌 미네랄과의 높이를 구하고 구간에서 가장 낮은 높이만큼 해당하는 미네랄 전체를 움직인다. 

[코드]

import java.lang.StringBuilder
import java.util.*

private var n = 0
private var m = 0
private lateinit var arr : Array<CharArray>
private lateinit var heights : IntArray
private val dx = listOf(1,-1,0,0)
private val dy = listOf(0,0,1,-1)
private val sb = StringBuilder()
fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    br.readLine().split(" ").map { it.toInt() }.apply {
        n = this[0]
        m = this[1]
    }
    arr = Array(n){ CharArray(m) }
    repeat(n){
        arr[it] = br.readLine().toCharArray()
    }
    val t = br.readLine().toInt()
    heights = br.readLine().split(" ").map { it.toInt() }.toIntArray()

    for(i in 0 until heights.size){
        if((i + 1) % 2 == 1 ){
            fromLeft(n-heights[i])

        }
        else {
            fromRight(n-heights[i])
        }
    }
    for(i in 0 until n){
        for(j in 0 until m){
            sb.append(arr[i][j])
        }
        sb.append("\n")
    }
    bw.write(sb.toString())
    bw.flush()
    bw.close()
}
private fun fromLeft(height : Int){
    for(i in 0 until m){
        if(arr[height][i] == 'x'){
            arr[height][i] = '.'
            for(k in 0 .. 3) {
                val nx = height + dx[k]
                val ny = i + dy[k]
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue
                if(arr[nx][ny] == '.') continue
                isConnectedAndMoveMinerals(nx,ny)
            }
            break
        }
    }
}
private fun fromRight(height : Int){
    for(i in m-1 downTo 0){
        if(arr[height][i] == 'x'){
            arr[height][i] = '.'
            for(k in 0 .. 3) {
                val nx = height + dx[k]
                val ny = i + dy[k]
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue
                if(arr[nx][ny] == '.') continue
                isConnectedAndMoveMinerals(nx,ny)
            }

            break
        }
    }
}
private fun isConnectedAndMoveMinerals(px: Int, py : Int)  {
    val queue : Queue<Pair<Int,Int>> = ArrayDeque()
    val visited : Array<BooleanArray> = Array(n){BooleanArray(m) }
    queue.add(Pair(px,py))
    visited[px][py] = true
    var minY = py
    var maxY = py
    var bool = false
    while(queue.isNotEmpty()){
        val (x,y) = queue.poll()
        for(i in 0 .. 3){
            val nx = x + dx[i]
            val ny = y + dy[i]
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue
            if(arr[nx][ny] == '.') continue
            if(visited[nx][ny]) continue
            if(nx == n - 1) bool = true
            queue.add(Pair(nx,ny))
            visited[nx][ny] = true
            minY = Math.min(ny,minY)
            maxY = Math.max(ny,maxY)
        }
    }
    if(!bool){
        var minHeight = 100

        val arrayList = arrayListOf<Pair<Int,Int>>()
        for(j in minY .. maxY){
            var curX = n
            for(i in n - 1 downTo 0){
                if(arr[i][j] == 'x'){
                    if(visited[i][j]){
                        arrayList.add(Pair(i,j))
                        minHeight = Math.min(minHeight,curX - i - 1)
                        break
                    }
                    else {
                        curX = i
                    }
                }

            }
        }
        arrayList.forEach {
            move(minHeight,it.first,it.second,visited)
        }
    }
}
private fun move(height : Int,sx: Int, sy: Int,visited :  Array<BooleanArray>){
    for(i in sx downTo  0){
        if(visited[i][sy]){
            arr[i + height][sy] = arr[i][sy]
            arr[i][sy] = '.'
        }
    }
}