[백준][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초가 지난 후의 격자판 상태를 출력한다.

🎈접근방법

1. 처음 폭탄의 위치에 따라 시간을 저장하는 배열을 만든다.
2. 처음 폭탄의 위치에는 3초를 저장한다.
3. 그 이후 폭탄을 설칠 할 때 해당 시간 + 3초를 저장한다.
4. 연쇄반응은 없기 때문에 3초가 되지 않은 폭탄들은 그냥 제거하면 된다.

🎈코드

package BaekJoon.P16918;

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

/**
 * https://www.acmicpc.net/problem/16918
 * [16918번: 봄버맨]-Silver
 */

public class Main {
    static int R,C,N;
    static char[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[][] times;
    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());

        map = new char[R+1][C+1];
        times = new int[R+1][C+1];

        for(int i=1; i<=R; i++){
            String str = br.readLine();
            for(int j=1; j<=C; j++){
                map[i][j] = str.charAt(j-1);
                if(map[i][j] == 'O'){
                    times[i][j] = 3;
                }
            }
        }
        search();
        print();
    }
    static void search(){
        int time=0;
        while(true) {
            if(time>=N) break;
            time++;
            // 폭탄이 설치 되어 있지 않은 모든 칸에 폭탄 설치
            if(time%2==0) {
                add(time);
            }else { // 터져야할 폭탄을 찾아서 파괴한다.
                for (int i = 1; i <= R; i++) {
                    for (int j = 1; j <= C; j++) {
                        if (times[i][j] == time) {
                            map[i][j] = '.'; // 해당 폭탄 파괴
                            times[i][j] = 0; // 시간 초기화
                            for (int k = 0; k < 4; k++) { // 상 하 좌 우 확인
                                int px = i + dx[k];
                                int py = j + dy[k];
                                if (px > 0 && py > 0 && px <= R && py <= C) {
                                    // 폭탄이면서 시간이 되지 않은 폭탄
                                    if(map[px][py]=='O' && times[px][py]!=time) {
                                        map[px][py] = '.';
                                        times[px][py] = 0;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    // 출력
    static void print(){
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=R; i++){
            for(int j=1; j<=C; j++){
                sb.append((map[i][j]));
            }
            sb.append('\n');
        }
        System.out.println(sb.toString());
    }
    // 폭탄 아닌 곳에 폭탄 설치하기
    static void add(int time){
        for(int i=1; i<=R; i++){
            for(int j=1; j<=C; j++){
                if(map[i][j]=='.'){
                    map[i][j]='O';
                    times[i][j] = time+3;
                }
            }
        }
    }
}

알고 넘어가기

첫 번째,

for(int i=1; i<=R; i++){
           for(int j=1; j<=C; j++){
               System.out.print(map[i][j]);
           }
           System.out.println();
       }

두 번째,

StringBuilder sb = new StringBuilder();
       for(int i=1; i<=R; i++){
           for(int j=1; j<=C; j++){
               sb.append((map[i][j]));
           }
           sb.append('\n');
       }
       System.out.println(sb.toString());

위처럼 StringBuilder로 출력하는 것이 거의 3배정도 빠른것으로 나타났다.