[백준 / BOJ] 16918 봄버맨 (Java)

문제

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

16918번: 봄버맨

R*C그리드가 있다.

0 초 - 봄버맨은 초기에 폭탄을 하나 설치한다. 

1 초 - 봄버맨은 초반 1초에는 아무것도 하지않는다.

2 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다.

3 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다.

4 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다.

.

.

.

 

위 과정을 N초까지 반복했을때 R*C그리드의 상태를 나타내는 문제다.

 

풀이

R이 200 C가 200 N이 200 이므로, 최악의경우 O(RCN) 시간복잡도가 나오므로 완전탐색으로도 시간안에 해결가능한 문제였다.

 

문제해설이 좀 어려웠는데, 나는 위 문제를 다음과 같이 해석하고 풀었다.

 

R*C그리드가 있다.

0 초 - 봄버맨은 초기에 폭탄을 하나 설치한다. 

1 초 - 봄버맨은 초반 1초에는 아무것도 하지않는다.

2 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다.

3 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다.

4 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다.

.

.

.

 

하지만, 문제에있는 힌트에는 1초에 폭탄을 설치하는거로 보아, 문제의 의도와는 조금 다르게 해석한듯하다. 어쨌든 결과는 잘 나왔으니..

 

핵심 코드는 아래와 같다.

private void simulator(int sec){
        if(sec > N) return;
        setBomb(sec);
        explode(sec);
        if(sec == N) return;
        simulator(sec+1);
    }
    
    private void setBomb(int sec){ // 폭탄을 설치한다.
        for(int i = 1; i <= R; i++){
            for(int j = 1; j <= C; j++){
                if(bomb[i][j] == -1) bomb[i][j] = sec; // 폭탄을 설치할수있는곳은 -1로 표시되어있다.
            }
        }
    }
    
    private void explode(int sec){ // 폭탄을 터친다.
        int temp[][] = new int[R+5][C+5]; // temp배열을 임시로 만들어 temp배열에 먼저 연산해놓는다.
        for(int i = 1; i <= R; i++){
            for(int j =1; j <= C; j++){
                if(bomb[i][j] != -1 && bomb[i][j]+3 == sec) { // 3초전 폭탄을 터트린다.
                	// 문제 본 의도대로 풀려한다면, 3초전 폭탄이아닌 2초전 폭탄을 터트려야 할것이다.
                    temp[i][j] = -1;
                    temp[i-1][j] = -1;
                    temp[i+1][j] = -1;
                    temp[i][j-1]= -1;
                    temp[i][j+1] = -1;
                }
            }
        }
        // 연산결과를 반영한다.
        for(int i = 1; i <= R; i++){
            for(int j =1; j <= C; j++){
                if(temp[i][j] == -1) bomb[i][j] = -1;
            }
        }
    }

소스코드

https://github.com/devxb/JJUNalgo/blob/master/16918%20%EB%B4%84%EB%B2%84%EB%A7%A8/Main.java

devxb/JJUNalgo