[백준] 16918번 : 봄버맨 - 자바[Java]

https://www.acmicpc.net/problem/16918

16918번: 봄버맨

풀이

문제를 이해하기 위해 직접 격자판과 폭탄을 그려보았다. 이 때 폭탄이 설치된 위치에는 폭탄이 설치된 초를 써넣었다. 백준의 예시를 봐도 확인할 수 있다.

이를 보면 2초 후 부터는 폭탄 채우기와 폭탄 터뜨리기가 번갈아 수행되는 것을 알 수 있었다.

따라서 int형 2차원 배열을 선언하여 빈 칸은 -1, 폭탄이 있으면 해당 폭탄이 설치된 초를 저장하도록 하여 로직을 수행하도록 했다.

 

로직

1. 먼저 격자 상태를 저장하기 위해 int[r][c] map을 선언한다.

2. 초기화: 초기에는 map을 -1(빈칸), 0(폭탄)으로 채운다.

3. 2초부터 다음 로직을 반복한다. 이때 폭탄 채우기와 폭탄 터뜨리기가 번갈아 수행되므로 second가 짝수일 때와 홀수일 때를 구분하여 수행한다.

3-1) second가 짝수일 때: 빈칸이 있으면 현재 초 수로 map 채우기

3-2) second가 홀수일 때: map에 있는 칸 중 (second - 3)인 폭탄이 있으면 폭탄과 주변을 터뜨리고 -1로 변환한다. 이 때 터뜨려야 하는 폭탄을 큐에 모두 넣은 다음 BFS와 유사한 로직을 사용하여 해당 폭탄과 주변을 터뜨린다.

4. 출력하기: 최종적으로 -1은 빈칸, 0이상의 숫자가 있는 칸은 폭탄으로 표시하여 출력한다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static int r;
    static int c;
    static int n;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    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 int[r][c];

        for (int i = 0; i < r; i++) {
            String line = br.readLine();

            for (int j = 0; j < c; j++) {
                char word = line.charAt(j);
                // 빈칸은 -1, 폭탄은 0으로 초기화
                if (word == '.') {
                    map[i][j] = -1;
                }
            }
        }

        for (int sec = 2; sec <= n; sec++) {
            if (sec % 2 == 0) {
                fillMap(sec);
            } else {
                bomb(sec);
            }
        }

        print();
    }

    static void fillMap(int sec) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == -1) {
                    map[i][j] = sec;
                }
            }
        }
    }

    static void bomb(int sec) {
        Queue<int[]> q = new ArrayDeque<>();

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == sec - 3) {
                    q.add(new int[]{i, j});
                }
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];

            map[x][y] = -1;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                    map[nx][ny] = -1;
                }
            }
        }
    }

    static void print() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == -1) {
                    sb.append('.');
                } else {
                    sb.append('O');
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

 

개선한 풀이

개선점

1. second가 짝수인 경우에는 무조건 모든 칸에 폭탄이 다 차므로, n이 짝수인 경우 각 초마다 수행을 할 필요 없이 폭탄이 꽉 찬 상태를 출력하면된다.

2. 폭탄을 터뜨릴 때 큐 없이 (second - 3)인 폭탄이 있으면 바로 폭탄과 주변을 터뜨리고 -1로 변환한다.

이 때 주의할 점은 주변에 있는 폭탄도 (second - 3)인 폭탄일 경우, -1로 변환하지 않고 그대로 둬야한다.

import java.io.*;
import java.util.*;

public class Main {

    static int r;
    static int c;
    static int n;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    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 int[r][c];

        for (int i = 0; i < r; i++) {
            String line = br.readLine();

            for (int j = 0; j < c; j++) {
                char word = line.charAt(j);
                // 빈칸은 -1, 폭탄은 0으로 초기화
                if (word == '.') {
                    map[i][j] = -1;
                }
            }
        }

        doBomberMan(n);
        print();
    }

    static void doBomberMan(int n) {
        if (n == 1) return;
        if (n % 2 == 0) {
            for (int i = 0; i < r; i++) {
                Arrays.fill(map[i], 0);
            }
            return;
        }

        for (int sec = 2; sec <= n; sec++) {
            if (sec % 2 == 0) {
                fillMap(sec);
            } else {
                bomb(sec);
            }
        }
    }

    static void fillMap(int sec) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == -1) {
                    map[i][j] = sec;
                }
            }
        }
    }

    static void bomb(int sec) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == sec - 3) {
                    map[i][j] = -1;

                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                            if (map[nx][ny] == sec - 3) continue; // 주의!
                            map[nx][ny] = -1;
                        }
                    }
                }
            }
        }
    }

    static void print() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == -1) {
                    sb.append('.');
                } else {
                    sb.append('O');
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

 

첫번째 풀이가 개선한 풀이, 마지막 풀이가 처음 풀이다. 큐를 쓰지 않았기 때문에 메모리 사용량이 대폭 감소되었으며 시간도 감소한 것을 확인할 수 있다.