[HackerRank] The Bomberman Game

출처: https://www.hackerrank.com/challenges/bomber-man/problem

(r, c) = 격자 크기 / 경과 시간 n

(6, 7) / n = 3 (n 초 후의 격자 상태를 출력하는 것)

(폭탄 'O' / 아닌 지역은 '.')

위와 같이 초기에 임의의 위치에 폭탄이 설치되어 있다. 

현재 시점에 설치되어 있는 폭탄은 3초뒤에 터진다.

　

[1초 후]

Bomberman은 아무런 행위를 하지 않는다.

이때는 '1초'의 시간이 흐른것 외에는 차이가 없다.

　

[2초 후]

Bomberman이 폭탄이 없었던 모든 영역에 새로운 폭탄을 설치한다.

이 시점에 설치된 폭탄은 지금으로부터 3초 뒤에 터진다.

　

[3초 후]

3초가 지나면서 초기에 설치되어 있던 폭탄들이 터진다.

이때, 폭발범위는 상하좌우 영역을 연쇄 폭파 한다.

상하좌우에 존재하는 다른 폭탄이 다른 영역에 영향을 끼치지는 않는다.

즉. 연결되어 있는 모든 폭탄이 터지는 것이 아니다.

 

n = 3이므로 위의 격자 상태를 출력하며 종료.

문제에서 주어지는 타이밍을 분석하면 Bomberman은 폭파할 때는 폭탄을 추가 매설하지 않는다.

ex. 폭탄이 터진 후 Bomberman이 바로 추가 폭탄을 매설하지 않고 다음 time으로 넘어간다.

      n=4인 경우, 1초 뒤 Bomberman이 폭탄이 없는 지역에 신규 폭탄을 설치한다.

 

[ 행: 시간 / 열: n번째 폭탄 ]

 

주어지는 N이 충분히 클 수 있다는 점에서  일정 시간 간격으로 반복되는 특성이 존재.

※ 초기 주어진 값으로부터 1초가 지난 뒤인 2초 부터는 4초 간격으로 grid의 양상이 동일함

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Solution {
    static int R, C;
    static int[][] grid;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);    
         
        R = sc.nextInt();
        C = sc.nextInt();
        int N = sc.nextInt();
         
        sc.nextLine();
         
        grid = new int[R][C];
         
        for(int i=0; i<R; i++) {
            String str = sc.nextLine();
            for(int j=0; j<C; j++) {
                if(str.charAt(j) == 'O') {
                    // 3초 후에 터치는 폭탄 매설
                    // 초기 1초 후에는 아무 변화가 없으므로 1초가 지난 시간으로 세팅
                    grid[i][j] = 2;
                }
            }
        }
 
        // Bomberman 활동 상태
        boolean isActive = true;
         
        // 폭발 범위 (상하좌우)
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
         
        // 위에서    1초가 지난 시점으로  세팅했으므로
        N--;
         
        // 초기 N > 1이라면 N이 큰 수치이면 timeout이 나므로 조절
        if(N > 0) {
            N = N % 4;
            if(N == 0) N = N + 4;    
        }
         
        // Bomberman이 반복하는 행위를 주어진 n에 맞게 수행(초기 부터 2초가 되는 시점부터 시뮬레이션)
        while(N-- > 0) {
            // Bomberman 활동 시기 (이 시점을 계산하면 터지는 폭탄은 없다.)
            if(isActive) {
                for(int i=0; i<R; i++) {
                    for(int j=0; j<C; j++) {
                        // 기존에 폭탄이 이미 있다면 countdown
                        if(grid[i][j] > 0) {
                            grid[i][j]--;
                        }else {
                            // 신규 폭탄 매설
                            grid[i][j] = 3;
                        }
                    }
                }
                isActive = !isActive;
            }else { // 폭발이 일어나는 타이밍으로 Bomberman이 관찰(observes)하는 시점
                 
                // 모든 폭탄을 한번에 처리하기 위해 따로 리스트에 담아둔다.
                List<Bomb> bombList = new ArrayList<>();
                for(int i=0; i<R; i++) {
                    for(int j=0; j<C; j++) {
                        // 매설되어 있는 모든 폭탄들을 countdown
                        if(grid[i][j] > 0) {
                            // 폭파되는 폭탄인지 확인
                            if(--grid[i][j] == 0) {
                                bombList.add(new Bomb(i, j));                                
                            }
                        }
                    }
                }
                // 임시저장해둔 폭탄을 일제히 폭파 시킨다.
                while(bombList.size() > 0) {
                    Bomb bomb = bombList.remove(0);
                    for(int d=0; d<dx.length; d++) {
                        // 주변 영역 destroy                    
                        int temp_x = bomb.x + dx[d];
                        int temp_y = bomb.y + dy[d];
                        // 격자를 벗어나면 skip
                        if(temp_x < 0 || temp_x >= R || temp_y < 0 || temp_y >= C) {
                            continue;
                        }
                        grid[temp_x][temp_y] = 0;
                    }
                }
                 
                isActive = !isActive;
            }
        }
         
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(grid[i][j] == 0) { // 폭탄이 존재 X.
                    System.out.print('.');    
                }else {
                    System.out.print('O');
                }
            }
            System.out.println();
        }
    }
}
 
class Bomb {
    int x;
    int y;
    Bomb(int x, int y){
        this.x = x;
        this.y = y;
    }
}