[BJ] 16918. 봄버맨

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

16918번: 봄버맨

 

✔ 문제 조건

1. 행 R <= 200, 열 <= 200
2. 폭탄이 설치되고 터지는 과정
   1. 초기(0초)에 일부 칸에만 폭탄을 설치해둠
   2. 1초 동안 아무것도 하지 않는다. -> 1초까지 아무 일도 일어나지 않는다.
   3. 다음 1초 동안 빈 칸에 모두 폭탄을 설치하기 시작한다. 모두 동시에 설치했다고 가정한다. -> 1초부터 2초까지 폭탄을 설치하기 때문에, 2초부터 모든 칸에 폭탄이 있다고 풀어야 한다. (이 부분을 이해 못해서 한참을 못풀었다;;)
   4. 1초가 지난 후 (3초부터) 3초 전에 설치된 폭탄이 모두 폭발한다.
      • 폭발하면서 4방향으로 인접한 폭탄들을 폭발시킨다.
   5. 3, 4번을 반복한다.

✔ 접근 과정

1. char형의 2차원 배열을 int형으로 바꾸어 저장한다. 빈칸은 -1로, 초기에 설치된 폭탄은 0초에 설치되었다는 의미로 0초로 초기화 한다.
2. 매 time초에 새롭게 설치되는 폭탄은 map의 값 time으로 변경한다.
3. 매 time초 마다 3초 전 (time-3)초에 설치된 폭탄은 폭발시킨다.
   • 폭발하면서 4방향으로 인접한 폭탄들을 폭발시킨다.
   • 4방향으로 탐색하며 똑같이 3초 전에 설치된 폭탄을 제외하고 폭발시켜야 한다. 3초 전에 설치된 폭탄은 동시에 터지며 또다시 인접한 폭탄을 폭발시켜야 하기 때문이다.

 

시뮬레이션 문제 오랜만에 푸니까 이틀 걸렸다 테스트 케이스 다 이해하고 코드짜자^^;;;;

import java.io.*;
import java.util.*;
// 210914

public class Main_BJ_16918_봄버맨 {
    static StringBuilder sb;
    static int R, C, N;
    static int[][] map;
    static int[] dr = new int[] {-1, 1, 0, 0};
    static int[] dc = new int[] {0, 0, -1, 1};
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("src/res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = stoi(st.nextToken());
        C = stoi(st.nextToken());
        N = stoi(st.nextToken()); // N초 후
        map = new int[R][C];

        for(int i=0; i<R; i++) {
            char[] tmp = br.readLine().toCharArray();
            for(int j=0; j<C; j++) {
                if(tmp[j]=='.') map[i][j] = -1;// 빈칸
                else map[i][j]=0; // 초기 폭탄
            }
        }

        for(int time=1; time<=N; time++) {
            // 빈칸에 폭탄 설치
            if (time>=2) install(time); // 1초부터 빈칸에 폭탄을 설치하기 시작했으면 2초에 설치가 모두 끝난 것
            // time-3에 설치된 폭탄들은 터진다.
            if(time>=3) bomb(time); // time=2에 빈칸(-1)을 -1초에 터진 것으로 인식 못하게
        }

        // 출력
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(map[i][j]==-1) sb.append('.');
                else sb.append('O');
            }
            if(i<R-1) sb.append("\n");
        }

        System.out.println(sb.toString());
        br.close();
    }

    static void install(int time) {
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(map[i][j]==-1) map[i][j] = time;
            }
        }
    }

    static void bomb(int time) {
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(map[i][j]==time-3) { // 3초 전에 터진 폭탄
                    map[i][j] = -1; // 폭탄 터짐
                    // 연쇄 작용으로 4방 탐색하여 폭탄 제거
                    for(int d=0; d<4; d++) {
                        int nr = i + dr[d];
                        int nc = j + dc[d];
                        if (valid(nr, nc) && map[nr][nc]!=-1 && map[nr][nc]!=time-3) {
                            map[nr][nc] = -1; // 폭탄 터짐
                        }
                    }
                }
            }
        }
    }

    static boolean valid(int nr, int nc) {
        if(nr<0 || nr>=R || nc<0 || nc>=C) return false;
        return true;
    }

    static int stoi(String str) {
        return Integer.parseInt(str);
    }
}