백준 16918번 (스터디)

문제

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
다음 1초 동안 봄버맨은 아무것도 하지 않는다.
다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
3과 4를 반복한다.
폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

예를 들어, 초기 상태가 아래와 같은 경우를 보자.

입력

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

출력

총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

---

요약

• t = 1

→ 입력 그대로 출력.

• 짝수 초(t = 2, 4, 6, …)

→ 모든 칸에 폭탄이 설치됨(전부 ‘O’).

• 홀수 초 중 특별한 두 패턴만 반복됨

t = 3 → 첫 번째 폭발
t = 5 → 두 번째 폭발
t = 7 → 다시 t=3 상태 반복
t = 9 → t=5 상태 반복

if n == 1 → 초기 맵
else if n % 2 == 0 → 전부 폭탄 맵
else if n % 4 == 3 → t=3 결과 맵
else if n % 4 == 1 → t=5 결과 맵

접근법

• 초기 맵 저장
• 전부 폭탄인 맵 생성
• 초기 맵 기준으로 폭발시킨 t=3 맵 생성
• t=3 맵 기준으로 폭발시킨 t=5 맵 생성
• 시간 n의 규칙에 따라 최종 출력 선택

코드

import java.util.*;

public class Main {

    static int R, C, N;      // 행, 열, 시간
    static char[][] initial; // 초기 입력 상태
    static char[][] full;    // 모든 칸이 폭탄인 상태 (짝수 초에서 사용)
    static char[][] boom1;   // 첫 번째 폭발 결과 (t=3)
    static char[][] boom2;   // 두 번째 폭발 결과 (t=5)

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력 크기 받기
        R = sc.nextInt();
        C = sc.nextInt();
        N = sc.nextInt();
        sc.nextLine(); // 개행 제거

        // 초기 맵 입력 받기
        initial = new char[R][C];
        for (int i = 0; i < R; i++) {
            initial[i] = sc.nextLine().toCharArray(); 
            // 한 줄씩 받고 char[]로 변환
        }

        full = makeFullBoard();    // 전부 'O'로 채운 맵 생성
        boom1 = explode(initial);  // t=3 결과 미리 계산
        boom2 = explode(boom1);    // t=5 결과 미리 계산

        print(selectBoard());      // 시간 N에 해당하는 최종 결과 출력
    }

    // ------------------ 최종 맵 선택 로직 ------------------

    // 시간 N에 따라 어떤 맵을 출력할지 결정하는 메서드
    private static char[][] selectBoard() {

        if (N == 1) return initial; // 1초는 입력 그대로

        if (N % 2 == 0) return full; 
        // 짝수 초는 무조건 모든 칸 폭탄 

        if (N % 4 == 3) return boom1; 
        // 3초, 7초, 11초… → 첫 번째 폭발 패턴 반복

        return boom2; 
        // 5초, 9초, 13초… → 두 번째 폭발 패턴 반복
    }

    // ------------------ 모든 칸 폭탄 보드 생성 ------------------

    private static char[][] makeFullBoard() {
        char[][] map = new char[R][C];  // 새로운 보드 생성
        for (int i = 0; i < R; i++) {
            Arrays.fill(map[i], 'O');  
            // 행 단위로 'O'로 채우기
        }
        return map;
    }

    // ------------------ 폭발 터뜨린 보드 생성 ------------------

    private static char[][] explode(char[][] board) {
        // 폭발 후 남는 영역은 폭탄으로 가득하므로 full보드 기반으로 시작
        char[][] next = makeFullBoard();

        // 폭발 범위 정의 (자기 자신 + 상하좌우)
        int[] dx = {1, -1, 0, 0, 0};
        int[] dy = {0, 0, 1, -1, 0};
        // dx, dy를 배열로 폭발 범위를 처리

        for (int x = 0; x < R; x++) {         // 모든 좌표 탐색
            for (int y = 0; y < C; y++) {

                if (board[x][y] == 'O') {     // 현재 위치에 폭탄이 있으면
                    for (int i = 0; i < 5; i++) { // 자기 + 상하좌우
                        int nx = x + dx[i];
                        int ny = y + dy[i];

                        // 보드 범위를 벗어나지 않는지 체크
                        if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                            next[nx][ny] = '.'; // 폭발 영향 → 비어있는 칸으로 변경
                        }
                    }
                }
            }
        }

        return next; // 폭발 이후의 새로운 보드 반환
    }

    // ------------------ 출력 담당 ------------------

    private static void print(char[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < R; i++) {
            sb.append(board[i]).append('\n'); 
            // char[] 바로 append하면 문자열로 붙어서 출력
        }

        System.out.print(sb); 
        // 마지막에 한 번만 출력
    }
}