[S1] 봄버맨 : Java : 16918 - BFS

1. 📄 문제

16918번: 봄버맨

 

 

 

2.  🤔 어떻게 접근할까

문제가 길어 차근 차근 그림으로 그리니 짝수와 홀수번으로 나누어졌다. 그래서 짝수와 홀수번 로직을 따로 구현한다로 생각했다.

또한 폭탄이 터지는 기준은 폭탄이 있는 위치에서 상하좌우 4개의 폭탄이 터져 없어지기 떄문에, 폭탄의 위치를 큐에 넣어 터질 시간이 되면 큐에서 꺼내어 상하좌우를 알아보기로 생각했다. 이 정도만 생각하고 바로 풀었는데 몇 몇 막히는 부분이 있었다.

 

 

3. 💡 생각해야 할 점

먼저, 폭탄은 설치 후 3초가 지나야 터진다는 것. 즉 폭탄이라고 무조건 터트리는 것이 아닌 이미 설치된 폭탄이라는 것을 알리는 표시가 필요했다. 그래서 '폭탄을 설치 하기 전'에 폭탄이 있는 위치를 `isImminent` 큐에 담고 폭탄이 없는 위치에는 `isBomb` 배열에 `ture` 값을 넣어 폭탄을 표시했다. 그 후 폭탄을 터트릴 떄 isImminent 큐에 담긴 모든 위치와 인접한 위치들의 폭탄을 터트렸다. 그 후 다시 폭탄을 설치할 때 앞서 isBomb이 ture인 경우를 다시 isImminent큐에 담아 이 과정은 반복적으로 일어난다.

 

또한 짝수 번째는 무조건 모든 위치에 폭탄이 놓아져 있다. 다른 사람 코드를 보다가 알게되었다.

 

 

4.  🖥️ 코드

코드를 봐보자

import java.awt.*;
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_봄버맨 {

    static BufferedReader br;
    static BufferedWriter bw;
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};
    public static boolean[][] isBomp;
    public static Queue<Point> isImminent;
    public static Queue<Point> que;

    public static void main(String[] args) throws Exception {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        isBomp = new boolean[R][C];
        que = new LinkedList();
        isImminent = new LinkedList();

        // 0초
        for (int r = 0; r < R; r++) {
            String[] info = br.readLine().split("");
            for (int c = 0; c < C; c++) {
                if (info[c].equals("O")) {
                    isBomp[r][c] = true;
                } else {
                    isBomp[r][c] = false;
                }
            }
        }
       
        int count = 1;

        while (++count <= N) {
            // 2(짝수) 폭탄이 없는 곳에 폭탄 설치
            if (count % 2 == 0) {
                for (int r = 0; r < isBomp.length; r++) {
                    for (int c = 0; c < isBomp[0].length; c++) {
                        if (!isBomp[r][c]) { // 폭탄이 없으면 설치
                            isBomp[r][c] = true;
                        } else {
                            isImminent.add(new Point(r, c)); // 곧 터질 폭탄
                        }
                    }
                }
            } else { // 폭탄 터트리기
                while (!isImminent.isEmpty()) {
                    Point p = isImminent.poll();
                    isBomp[p.x][p.y] = false;

                    for (int i = 0; i < dx.length; i++) {
                        int curX = p.x + dx[i];
                        int curY = p.y + dy[i];
                        if (curX >= 0 && curX < R && curY >= 0 && curY < C)
                            isBomp[curX][curY] = false;
                    }
                }
            }
        }
        print();
    }

    public static void print() throws IOException {
        for (int r = 0; r < isBomp.length; r++) {
            for (int c = 0; c < isBomp[0].length; c++) {
                if (isBomp[r][c]) {
                    bw.write("O");
                } else {
                    bw.write(".");
                }
            }
            bw.write("\n");
        }
        bw.flush();
    }
}