[BOJ] 16918: 봄버맨 (JAVA)

문제

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

 

여담

처음 문제를 읽고 어려울 것 같아 겁을 먹었지만 문제에서 주어지는 힌트를 통해 쉽게 풀이를 떠올릴 수 있었다. 그렇지만 코테에서는 이런 힌트가 잘 주어지지 않으니까 문제만 보고 풀 수 있도록 노력해야 되겠다.

 

풀이

이 문제는 다음과 같은 규칙으로 진행된다. 

• 처음 & 1초: 아무것도 하지 않음
• 2초: 모든 칸에 폭탄 설치
• 3초: 3초 전에 설치한 폭탄 폭발
• 4초: 모든 칸에 폭탄 설치
• 4초: 3초 전에 설치한 폭탄 폭발
• ...

 

위의 규칙을 통해 짝수 초일 때는 모든 칸에 폭탄이 설치되는 상태가 된다는 것을 알 수 있다. 따라서 N이 2의 배수라면 모든 칸에 폭탄이 설치된 상태를 출력하면 된다.

 

홀수 초일 때는 폭발이 발생한다. 즉, 2초마다 폭발이 발생한다. (3초, 5초, 7초, ...)

 

폭탄은 상하좌우로 폭발하기 때문에 폭발시킬 때 BFS 탐색을 수행하면 된다. 만약 1초가 지난 후의 상태를 확인하는 것이라면 아무 일도 일어나지 않은 상태이므로 입력받은 상태 그대로 출력하면 된다. 

 

그렇지 않다면 폭탄이 설치된 위치를 기록한 후, 폭탄이 위치한 자리와 그 자리의 상하좌우를 폭발시킨다. 그 후, 2초를 증가시킨 뒤 앞의 과정을 반복하면 된다. 

 

즉, 정리하면 다음과 같다.

1. 폭탄이 설치된 위치를 기록하기
   • if (map[i][j] == 'O') queue.offer(new int[]{i, j})
2. 폭탄을 폭발 시키기 (O → .)
   • 상하좌우에 위치하는 폭탄까지 폭발시키기
3. 2초 증가시키기 
4. N초가 될 때까지 1번 ~ 3번 반복하기

 

코드

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

public class Main {
    static int R, C, N;
    static char[][] map, full;
    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][C];
        full = new char[R][C];
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);
            }
            Arrays.fill(full[i], 'O');
        }

        if (N % 2 == 0) { // 2의 배수 초라면 폭탄으로 가득찬 상태
            print(full);
            return;
        }

        int time = 1;
        while (time != N) {
            bfs();
            time += 2;
        }
        print(map);
    }

    public static void print(char[][] arr) { // 출력을 위한 메소드
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                sb.append(arr[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    static char[][] copyArr(char[][] arr) {
        char[][] tmp = new char[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                tmp[i][j] = arr[i][j];
            }
        }
        return tmp;
    }

    static void bfs() {
        // 폭탄이 설치된 위치 기록하기
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'O') queue.offer(new int[]{i, j});
            }
        }

        // 폭발시키기
        char[][] tmp = copyArr(full); // 폭탄으로 가득찬 상태에서 폭발이 발생함
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            tmp[now[0]][now[1]] = '.';

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx < 0 || ny < 0 || nx >= R || ny >= C || tmp[nx][ny] == '.') {
                    continue;
                }

                tmp[nx][ny] = '.';
            }
        }
        map = copyArr(tmp);
    }
}

---