[백준/JAVA] 16918번: 봄버맨

📖 문제

16918번: 봄버맨

 

 

💡  풀이 방식

• 구현, 시뮬레이션

필요 자료구조
- 인접한 4방향 탐색용 dx/dy배열
- 폭탄 터질 시간 기록용 2차원 배열 timeArr ⭐
- 폭탄이 터질 시간나타내는 int형 변수 time (⚠ 1부터 시작!!)

 

 

1. 격자를 입력받으면서, 폭탄인 경우 폭탄 터질 시간을 기록한다.

if(board[i][j] == 'O')
    timeArr[i][j] = 3;  // 폭탄 터질 시간 (놓인 시간 +3)

 

 

2. 0초에는 아무 것도 하지 않고, 1초: 가만히 있음 > 2초: 폭탄 설치 > 3초: 폭발 > 4초: 폭탄 설치 > 5초: 폭발 > ,,, 이므로

시간은 1초부터 홀수/짝수 초에 맞춰 단계를 진행한다.

• 시간이 짝수 초라면, 비어있는 모든 칸에 폭탄을 설치한다. 설치할 때, 터질 시간도 함께 기록한다.

if(time % 2 == 0) { // 비어있는 모든 칸에 폭탄 설치
    for(int i = 0 ; i < R ; i++) {
        for(int j = 0 ; j < C ; j++) {
            if(board[i][j] == '.') {
                board[i][j] = 'O';
                timeArr[i][j] = time +3;	// 폭탄 터질 시간 기록
            }
        }
    }
 }

 

 

• 시간이 홀수 초라면, 시간이 다 된 폭탄을 터트린다. 그리고 인접한 4방향을 탐색해서 현재 시간에 터트리지 않는 폭탄인 경우에만 폭발시킨다. (현재 시간에 터지는 폭탄을 폭발시켰다간 예외가 발생할 수 있으므로)

else if(time % 2 == 1) {    // 폭탄 터지기
    for(int i = 0 ; i < R ; i++) {
        for(int j = 0 ; j < C ; j++) {
            if(timeArr[i][j] == time) { // 시간이 다 된 폭탄 터트리기
                board[i][j] = '.';

                for(int d = 0 ; d < 4 ; d++) {  // 인접4방향 터트리기
                    int nx = i + dx[d];
                    int ny = j + dy[d];

                    if(nx < 0 || nx >= R || ny < 0 || ny >= C)  continue;
                    if(board[nx][ny] == 'O') {
                        if(timeArr[nx][ny] != time) {   // ⭐ 현재 시간에 터트리지 않는 폭탄만 폭발
                            board[nx][ny] = '.';
                            timeArr[nx][ny] = 0;
                        }
                    }
                }
            }
        }
    }
 }

 

 

 

 

💥 유의사항

• 폭탄을 터뜨릴 때, 그 주변 폭탄이 이번 time에 터트려야 할 폭탄이라면, 폭발시키지 않는다! 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int R,C,N;
    static char[][] board;
    static int[][] timeArr; // ⭐ 폭탄 놓인 시간 기록용 배열
    static int time;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        
        board = new char[R][C];
        timeArr = new int[R][C];
        
        for(int i = 0 ; i < R ; i++) {
            char[] ch = br.readLine().toCharArray();
            for(int j = 0 ; j < C ; j++) {
                board[i][j] = ch[j];
                
                if(board[i][j] == 'O')
                    timeArr[i][j] = 3;  // 폭탄 터질 시간 (놓인 시간 +3)
            }
        }
        
        time = 1;   // 💥 1초부터 시작 !!
        while(time <= N) {
            if(time % 2 == 0) { // 비어있는 모든 칸에 폭탄 설치
                installBombs();
            }
            else if(time % 2 == 1) { // 폭탄 터지기
                boom();
            }
            
            time++;
        }
        
        printArray();   // 결과 출력하기
    }
    
    private static void installBombs() {
        for(int i = 0 ; i < R ; i++) {
            for(int j = 0 ; j < C ; j++) {
                if(board[i][j] == '.') {    // 비어있는 모든 칸에 폭탄 설치
                    board[i][j] = 'O';
                    timeArr[i][j] = time +3;
                }
            }
        }
    }
    
    private static void boom() {
        for(int i = 0 ; i < R ; i++) {
            for(int j = 0 ; j < C ; j++) {
                if(timeArr[i][j] == time) { // 시간이 다 된 폭탄 터트리기
                    board[i][j] = '.';
                    
                    for(int d = 0 ; d < 4 ; d++) {  // 인접한 4방향 터트리기
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        
                        if(nx < 0 || nx >= R || ny < 0 || ny >= C)  continue;
                        if(board[nx][ny] == 'O') {
                            if(timeArr[nx][ny] != time) {   // ⭐ 현재 시간에 터트리지 않는 폭탄만 폭발
                                board[nx][ny] = '.';
                                timeArr[nx][ny] = 0;
                            }
                        }
                    }
                }
            }
        }
    }
    
    private static void printArray() {
        StringBuilder sb = new StringBuilder();
        for(char[] ch : board) {
            for(char c : ch) {
                sb.append(c);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());        
    }
}
 

 

---

💦 어려웠던 점

- 3초 전을 어떻게 찾지? 하고 리스트에 폭탄 위치와 시간 정보를 저장해서 할까? 라고 생각했었다.

- timeArr 쓸 생각만 했어도 이렇게 꼬여서 생각하지 않았을 듯

- 시간 어떻게 처리하지,,,의 문제 (1초를 제외하고 홀짝에 맞춰 반복하며 진행한다는 점을 늦게 깨달았다)

 

 

 

🧐 새로 알게 된 내용

- 위치마다 시간을 어떻게 기록할지 : 그냥 2차원 배열에 저장하도록 한다.

- 비어있는 모든 칸에 폭탄 설치하면서, 폭탄 시간 저장 배열에 폭탄 시간도 저장하는 아이디어,,,

- 인접한 4칸의 폭탄 터트릴 때도 그냥 터트리는 게 아니라, 현재 시간에 터트리지 않는 폭탄이어야 한다는 조건을 상기시키는 것

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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