boj 16918 봄버맨

www.acmicpc.net/problem/16918

16918번: 봄버맨

1. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치합니다. (입력으로 주어집니다.)

2. 1초 후에 봄버맨은 아무것도 하지않습니다.

3. 다음 1초 후에 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 동시에 설치합니다.

4. 다음 1초 후에 3초전에 설치했던 폭탄이 터집니다. 이때 바로 옆 공간의 폭탄도 터집니다.

5. 이후 3과 4를 반복합니다.

 

저는 폭탄을 나타내는 char형 배열과 시간(카운트)를 나타내는 int형 배열을 사용하였습니다.

3번 4번 과정을 반복하고, 처음 1번과정은 입력으로 주어진 후 1초동안은 아무것도 하지않기때문에

K를 1빼주고 처음 입력으로 주어진 폭탄들의 시간은 2초로 해줍니다.

 

그리고 반복문은 2초부터 돌려줍니다.

폭탄은 짝수 초에 터지고, 홀수 초에 놓아지기때문에 홀, 짝으로 나누어 구현하였습니다.

 

폭탄을 놓을 때는 시간이 0인 모든 공간에 놓아주었고, 시간이 0이 아니면 1 감소시켰습니다.

폭탄을 터뜨릴 때는 터져야할 모든 폭탄을 덱에 넣고, bfs방식으로 인접한 폭탄들을 함께 터뜨렸습니다.

마지막으로 K초가 지난 후의 격자판 상태를 출력해주시면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Deque<int[]> dq = new ArrayDeque<>();
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static char list[][];
    static int time[][];
    static int N, M, K;
 
    static void print() {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++)
                sb.append(list[i][j]);
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
 
    static void bfs() {
        while (!dq.isEmpty()) {
            int x = dq.peekFirst()[0];
            int y = dq.pollFirst()[1];
            
            for (int k = 0; k < 4; k++) {
                int nx = x + direct[k][0];
                int ny = y + direct[k][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                time[nx][ny] = 0;
                list[nx][ny] = '.';
            }
        }
    }
 
    static void func() {
        for (int t = 1; t <= K; t++) {
            if (t % 2 != 0) {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (time[i][j] == 0) {
                            list[i][j] = 'O';
                            time[i][j] = 3;
                        } else
                            time[i][j]--;
                    }
                }
            } else {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (time[i][j] == 0)
                            continue;
                        time[i][j]--;
                        if (time[i][j] == 0) {
                            list[i][j] = '.';
                            dq.addLast(new int[] { i, j });
                        }
                    }
                }
 
                bfs();
            }
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken()) - 1;
        time = new int[N][M];
        list = new char[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            for (int j = 0; j < M; j++) {
                if (list[i][j] == 'O') {
                    time[i][j] = 2;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}