백준 16918 봄버맨 Kotlin (시뮬레이션)

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

16918번: 봄버맨

문제

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

• 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
• 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
• 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
• 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
• 3과 4를 반복한다.

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

예를 들어, 초기 상태가 아래와 같은 경우를 보자.

...
.O.
...

1초가 지난 후에는 아무 일도 벌어지지 않기 때문에, 위와 같다고 볼 수 있다. 1초가 더 흐른 후에 격자판의 상태는 아래와 같아진다.

OOO
OOO
OOO

1초가 지난 후엔 가운데에 있는 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.

O.O
...
O.O

입력

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

출력

총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

힌트

아래는 시간이 지난 후 예제 격자판의 상태이다.

.......
...O...
....O..
.......
OO.....
OO.....

<초기 상태, 1초 후>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

<2초 후>

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

<3초 후>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

<4초 후>

.......
...O...
....O..
.......
OO.....
OO.....

<5초 후>

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 시뮬레이션

풀이

3달 전 풀다가 포기했던 문제다.

지금 다시 푸니까 쉽게 풀렸다.

나, 성장한 건가?

우선 시간대 별로 상태를 확인해 보자.

0초 : 그대로

1초 : 그대로

2초 : 폭탄 추가(그래프가 모두 폭탄으로 채워짐)

3초 : 초기 폭탄 폭발

4초 : 폭탄 추가

5초 : 2초에 설치한 폭탄 폭발

6초 : 폭탄 추가

7초 : 4초에 설치한 폭탄 폭발

 

위의 상태를 보니, 2초마다 폭탄이 추가되고, 3초부터 +2초마다 폭탄이 폭발한다.

 

폭탄은 두 종류가 있다.

먼저 터질 폭탄과, 나중에 터질 폭탄

이를 구분하기 위해

폭탄이 없는 칸 : 0

먼저 터질 폭탄이 있는 칸 : 1

나중에 터질 폭탄이 있는 칸 : 2

로 설정한다.

 

폭탄 설치는 2초마다 0인 칸을 2로 바꿔주는 것으로 구현하고,

폭발은 기존 그래프를 복사하며, 기존 그래프의 나중에 터질 폭탄(2)를 현재 터질 폭탄(1)로 갱신해 준다.

이후, 복사한 그래프에 있는 현재 터질 폭탄(1)을 모두 터트리고, 터트린 후의 상태는 기존 그래프에 갱신해 준다.

이 과정이 끝나면 기존 그래프에는 현재 터질 폭탄(1)은 모두 터져있고, 나중에 터질 폭탄(2)은 현재 터질 폭탄(1)로 갱신되어 있다.

 

 

코드

//1초 아무것도x
//2초 폭탄 설치되어있지 않은 모든 칸에 설치 ( 모든 칸에 폭탄이 설치됨)
//3초 3초 전에 설치된 폭탄 모두 폭발
//1<=r,c,n<=200
//터져야될 폭탄 1 나중 폭탄 2

val dir = arrayOf(
    intArrayOf(1,0),
    intArrayOf(0,1),
    intArrayOf(-1,0),
    intArrayOf(0,-1)
)

fun install(r: Int, c : Int, graph: Array<IntArray>){
    for(i in 0 until r){
        for(j in 0 until c){
            if(graph[i][j]==0){
                graph[i][j]=2
            }
        }
    }
}

fun bomb(r : Int, c : Int, graph: Array<IntArray>){
    val graphCopy = Array(r){IntArray(c)}
    //복사하면서 나중 폭탄을 1로 변경
    for(i in 0 until r){
        for(j in 0 until c){
            graphCopy[i][j] = graph[i][j]
            if(graph[i][j]==2){
                graph[i][j]=1
            }
        }
    }
    for(i in 0 until r){
        for(j in 0 until c){
            if(graphCopy[i][j]==1){
                graph[i][j] =0
                for(k in 0 until 4){
                    val nr = i+dir[k][0]
                    val nc = j+dir[k][1]
                    if(nr !in 0 until r || nc !in 0 until c) continue
                    graph[nr][nc] =0
                }
            }
        }
    }
}

fun play(r : Int, c : Int, n : Int, graph: Array<IntArray>){
    var time=0
    var bombTime =3
    while(time++<n){
        //설치
        if(time%2==0){
            install(r,c,graph)
        }
        if(time==bombTime){
            bomb(r,c,graph)
            bombTime +=2
        }
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (r,c,n) = br.readLine().split(' ').map{it.toInt()}
    val graph = Array(r){r->
        val line = br.readLine()
        var idx=0
        IntArray(c){c->
            if(line[idx++]=='.') 0 else 1
        }
    }
    play(r,c,n,graph)
    for(i in 0 until r){
        for(j in 0 until c){
            if(graph[i][j]==0){
                write(".")
            }
            else{
                write("O")
            }
        }
        write("\n")
    }
    close()
}