[백준] 16918 : 봄버맨 (JAVA/자바)

문제

BOJ 16918 : 봄버맨 - https://www.acmicpc.net/problem/16918

풀이

문제 이해부터 난관이었는데, 내가 이해한 바는 이렇다.

0초 - 초기상태
1초 - 가만히있음
2초 - 폭탄놓음
3초 뒤 - 폭탄터짐 (0초에 놓은거)
4초 - 폭탄 놓음
5초 뒤 - 폭탄터짐 (2초에 놓은거)
6초 - 폭탄 놓음
7초 뒤 - 폭탄터짐 (4초에 놓은거)
...

위와 같은 규칙(?)이 있었다. 1초동안은 아무것도 안한다, 3초 후에 터진다 이런 조건들이 왜 있나 했더니 이유가 있었다..

아무튼 N이 1부터 시작이기 때문에, time의 초깃값을 1로 설정하고 하나씩 올려가며 해당 time에 맞는 작업들을 해주면 된다. 홀수 초에는 폭탄이 터지고(1초 제외), 짝수 초에는 폭탄을 놓는다.

폭탄을 놓을 때는 비어있는 칸에bombtime 이중배열을 선언해 폭탄들이 놓인 시간 + 3==폭탄이 터질 time을 저장해주었다. 터트릴 땐 bombtime의 값이 time과 동일한지만 확인하여 터트리면 된다.

그리고 폭탄을 터트릴 때는 유의해야 할 점이 있는데, 연쇄반응으로 주변 폭탄을 터트릴 때 그 주변 폭탄이 이번 time에 터트려야 할 폭탄이라면 연쇄반응으로 터트리지 않는다. 왜냐하면 이번에 터트려야 할 폭탄을 연쇄반응으로 미리 터트리게 되면 미리 터트린 폭탄의 주변 폭탄을 연쇄시킬 수 없어 예외 케이스가 생기게 된다!

또 하나 더, 문제를 보고 1초에는 아무것도 하지 않기 때문에 2초부터 보면 되겠다! 라고 생각해서 time을 2로 초기화해서 풀이했는데 이럴 경우 틀렸습니다가 나온다. N이 1부터 시작이기 때문에 1부터 시작해야한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int R = Integer.parseInt(inputs[0]);
        int C = Integer.parseInt(inputs[1]);
        int N = Integer.parseInt(inputs[2]);

        char[][] map = new char[R][C];
        int[][] bombtime = new int[R][C];

        for (int i = 0; i < R; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = tmp.charAt(j);
                if(map[i][j]=='O'){
                    bombtime[i][j] = 3; // 폭탄이 터질 시간 (놓인 시간 + 3)
                }
            }
        }

        int time = 0;
        int[] mi = {1, -1, 0, 0};
        int[] mj = {0, 0, 1, -1};

        while(time++ < N) {

            if(time%2==0) {
                // 비어있는 모든 칸에 폭탄을 설치
                for (int i = 0; i < R; i++) {
                    for (int j = 0; j < C; j++) {
                        if (map[i][j] == '.') {
                            map[i][j] = 'O';
                            bombtime[i][j] = time+3;
                        }
                    }
                }
            }else if(time%2==1) {
                // 시간이 다 된 폭탄 터트림
                for (int i = 0; i < R; i++) {
                    for (int j = 0; j < C; j++) {
                        if (bombtime[i][j] == time) {
                            map[i][j] = '.';
                            for (int d = 0; d < 4; d++) {
                                int ni = i + mi[d];
                                int nj = j + mj[d];

                                if (ni < 0 || nj < 0 || ni >= R || nj >= C) continue;
                                
                                // 이번에 터트려야 할 폭탄을 연쇄반응으로 미리 터트리게 되면 
                                // 미리 터트린 폭탄의 주변 폭탄을 연쇄시킬 수 없다. 그래서 bombtime을 확인!
                                if(map[ni][nj]=='O' && bombtime[ni][nj] != time) { 
                                    map[ni][nj] = '.';
                                    bombtime[ni][nj] = 0;
                                }
                            }
                        }
                    }
                }
            }
        }

       
        for (int i = 0; i < R; i++) {
            System.out.println(map[i]);
        }

    }
}

정리

✔ 알고리즘 분류 - 구현, 그래프 이론, 그래프 탐색
✔ 난이도 - ⚪ Silver 1

🤦‍♀️ 오늘의 메모

• 오랜만에 몇시간을 삽질한 문제다.. 정답률 보면 그렇게 크게 어려울만한 문제가 아닌거 같은데 문제 이해부터 풀이까지 너무 어려웠다.

• while문을 탈출하는 조건에 엄청 헤맸다. 제출 코드에서는 while(time++<N)와 같이 썼는데 이는 아래 코드와 동일하다.

while(true){
    	...
   
    if(time>=N) break;
    time ++;
}

• while(time++<N) 은 일단 time<N의 조건을 확인한 뒤, while문이 끝나면 time을 +1 해주는 순서이다! 잘 알아둘 것.
  
  

참고 사이트

딱히 없음