백준 2933 미네랄 Kotlin (시뮬레이션)

문제 출처 : https://www.acmicpc.net/problem/2933

2933번: 미네랄

문제

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

입력

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

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

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

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

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

출력

입력 형식과 같은 형식으로 미네랄 모양을 출력한다.

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

풀이

전체적인 풀이는 다음과 같다.

1. 인덱스로 짝/홀을 구분하여 왼쪽/오른쪽에서 미네랄을 제거한다.

2. 미네랄을 제거한 후 공중에 뜬 클러스터와 바닥에 붙은 클러스터를 분리한다.

3. 공중에 뜬 클러스터를 그룹핑한다. (문제 조건상 공중에 뜬 클러스터는 한 그룹만 나온다고 한다.)

4. 공중에 뜬 클러스터를 내린다.

5. 1~4과정을 반복한다.

 

재사용 생각하지 말고 그냥 차분히 한 단계씩 구현하자.

1번 과정은 쉬우니 패스

2번 과정은 n-1(바닥 행)의 미네랄들을 bfs로 인접 4방향 훑어주어 1로 체크한다. (땅에 붙어있는 클러스터라는 의미)

3번 과정도 bfs로 땅에 붙어있는(1) 애들을 제외하고 나머지 미네랄을 찾아 그룹핑한다.

2번, 3번 과정에서 clusterMap을 사용했고 여기에 Int로 클러스터들을 구분하였다.

4번 과정은 그냥 구현이다. 본인은 클러스터의 가장 밑부분들이 바닥에 닿거나 1인 클러스터를 만나면 내리는 것을 멈췄다.

결과는 Fail

 반례는 다음과 같다. (https://www.acmicpc.net/board/view/59036)

9 8
........
.xxxx...
.x......
.x.xxxx.
.x....x.
.x....x.
.xxxx.x.
....xxx.
......x.
1
2

output:
........
........
.xxxx...
.x.xxxx.
.x....x.
.x....x.
.x....x.
.xxxxxx.
......x.

 

 

문제에는 다음과 같은 조건이 있다.

"클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다."

아니 그럼 'ㄷ' 모양의 공중 클러스터의 아래 부분 중 하나가 무조건 바닥 또는 미네랄 위로 떨어진다는 거 아니었냐고~~

각 열의 맨 아래 부분이면  6행에 1,2,3,4열을 가리키는 게 아닌가..

아무튼 저렇게 바닥에 닿지 않더라도 다른 클러스터에 걸치는 것도 고려해주어야 한다.

본인은 그냥 먼저 2중 포문 돌려서 걸치는지 먼저 확인하고 걸친다면 내리지 않게끔 구현해 주었다.

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

lateinit var map: Array<CharArray>
lateinit var clusterMap: Array<IntArray>
val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0)
)

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, m) = getIntList()
    map = Array(n) { br.readLine().toCharArray() }
    getInt()
    //solve
    getIntList().forEachIndexed { idx, h ->
        shoot(idx, n - h, n, m)
    }
    //output
    for(r in 0 until n){
        for(c in 0 until m){
            write("${map[r][c]}")
        }
        write("\n")
    }
    close()
}

fun shoot(idx: Int, h: Int, n: Int, m: Int) {
    when (idx and 1 == 0) {
        true -> leftShoot(h, m)
        false -> rightShoot(h, m)
    }
    moveMap(n, m)
}

fun moveMap(n: Int, m: Int) {
    clusterMap = Array(n){ IntArray(m) }
    //seperate cluster
    for (c in 0 until m) {
        if (map[n - 1][c] == 'x' && clusterMap[n - 1][c] != 1) {
            seperate(n - 1, c, n, m)
        }
    }

    var num = 2
    for(r in 0 until n) {
        for (c in 0 until m) {
            if (map[r][c] == 'x' && clusterMap[r][c] == 0) {
                groupingCluster(r, c, num++, n, m)
            }
        }
    }

    while(--num>1){
        while (true){
            if(downMap(num, n,m)) break
        }
    }

    for(r in 0 until n){
        for(c in 0 until m){
            map[r][c] = if(clusterMap[r][c]==0)'.' else 'x'
        }
    }

}

fun groupingCluster(sr: Int, sc: Int, num: Int, n: Int, m: Int) {
    val q: Queue<Pair<Int,Int>> = LinkedList()
    q.add(Pair(sr,sc))
    clusterMap[sr][sc] = num
    while (q.isNotEmpty()){
        val (cr,cc) = q.poll()
        for(i in 0 until 4){
            val nr = cr + dir[i][0]
            val nc = cc + dir[i][1]
            if(nr !in 0 until n || nc !in 0 until m) continue
            if(clusterMap[nr][nc] == num) continue
            if(map[nr][nc] == '.') continue
            clusterMap[nr][nc] = num
            q.add(Pair(nr,nc))
        }
    }
}


fun seperate(sr: Int, sc: Int, n: Int, m: Int) {
    val q: Queue<Pair<Int, Int>> = LinkedList()
    q.add(Pair(sr,sc))
    clusterMap[sr][sc] = 1
    while (q.isNotEmpty()){
        val (cr,cc) = q.poll()
        for(i in 0 until 4){
            val nr = cr + dir[i][0]
            val nc = cc + dir[i][1]
            if(nr !in 0 until n || nc !in 0 until m) continue
            if(clusterMap[nr][nc]==1) continue
            if(map[nr][nc] =='.') continue
            clusterMap[nr][nc] = 1
            q.add(Pair(nr,nc))
        }
    }
}

fun downMap(num: Int, n: Int, m: Int): Boolean {
    for(r in 0 until n-1){
        for(c in 0 until m){
            if(clusterMap[r][c] == 2 &&clusterMap[r+1][c] ==1) return true
        }
    }
    for(r in n-1 downTo  0){
        for(c in 0 until  m){
            if(clusterMap[r][c] == num){
                if(r + 1 >= n ){
                  return true
                }else{
                    if(clusterMap[r+1][c] !=0){
                        return true
                    }else{
                        clusterMap[r][c] = 0
                        clusterMap[r+1][c] = num
                    }
                }
            }
        }
    }
    return false
}


fun rightShoot(h: Int, m: Int) {
    for (c in m - 1 downTo 0) {
        if (map[h][c] == 'x') {
            map[h][c] = '.'
            return
        }
    }
}

fun leftShoot(h: Int, m: Int) {
    for (c in 0 until m) {
        if (map[h][c] == 'x') {
            map[h][c] = '.'
            return
        }
    }
}