[BOJ] 16919번 봄버맨 2 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int R, C, N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        init();
        if (N % 2 == 0) {
            set(N);
        } else {
            // n 초에 터지게 값 저장
            for (int n = 2; n <= N; n++) {
                N = N % 4 + 4;
                // 폭탄 설치
                if (n % 2 == 0) {
                    set(n);
                } else {
                    bomb(n);
                }
            }
        }
        printArray();
    }

    private static void init() 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 s = br.readLine();
            for (int j = 0; j < C; j++) {
                if (s.charAt(j) == '.') {
                    map[i][j] = 0;
                } else {
                    map[i][j] = 3;
                }
            }
        }
    }

    private static void set(int n) {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 0) map[i][j] = n + 3;
            }
        }
    }

    private static void bomb(int n) {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (map[r][c] == n) {
                    map[r][c] = 0;
                    for (int i = 0; i < 4; i++) {
                        int nr = r + dr[i];
                        int nc = c + dc[i];
                        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
                        if (map[nr][nc] == n) continue;
                        map[nr][nc] = 0;
                    }
                }
            }
        }
    }

    private static void printArray() {
        for (int[] ints : map) {
            for (int i : ints) {
                if (i == 0) System.out.print(".");
                else System.out.print("O");
            }
            System.out.println();
        }
    }

}

📄 해설

• 문제의 힌트를 보고 꼭!! 예제 대로만 출력하지 말고 N 의 값을 증가시켜서 출력해볼 것
• 단순 구현 문제이고 (단순하지는 않음), N 의 크기가 굉장히 큰 문제
• 알고리즘을 사용하는 것이 아니므로, 접근에 대한 설명을 하겠음
• 문제에서 요구하는 코드의 작동 방식에 대한 접근은 쉽게 했으나, 너무 큰 N 의 크기로 인해, N 을 조작하지 않으면 시간초과가 발생하는 문제

접근

• N 이 짝수인 경우와 홀수인 경우가 다르다 (2초마다 폭탄 설치, 3초마다 폭탄 폭파)
  -> 짝수인 경우는 항상 같은 결과
  -> 홀수인 경우는 반복적인 결과
  위 두개의 접근을 해내었다면, 끝이난 것
• 홀수, 짝수마다의 동작이 정해져 있고, 2초부터 본격적인 동작이 시작하므로, 2부터 N 까지 반복 수행
  • 짝수 초에는 폭탄을 설치하므로, 같은 결과 => 짝수인 경우는 다 채운다음 바로 출력
  • 홀수 초에는 현재 초와 같은 값을 가지고 있는 폭탄을 터트림 => 홀수인 경우는 반복문 수행
• 결과를 쭈욱 출력해보면, 특정 결과가 계속해서 반복이된다는 것을 확인 할 수 있고, 이것이 4번마다 반복되는 것을 확인할 수 있음
• '그렇다면 N %= 4 로 하면 끝이겠네' 하면, 예제만 맞고 틀린다 (작성자 얘기 아님)
  간단한 반례를 들어보자면, 입력이 아래와 같이 들어왔을 때, 모든 경우를 출력해보면 된다.

입력

2 2 11
.O
O.

출력

==========2==========
OO
OO
==========3==========
..
..
==========4==========
OO
OO
==========5==========
OO
OO
==========6==========
OO
OO
==========7==========
..
..
==========8==========
OO
OO
==========9==========
OO
OO
==========10==========
OO
OO
==========11==========
..
..

• 위 경우를 보게되면, 단순히 4개씩 반복되는 것이 아니라, 4~7, 8~9 가 반복됨을 알 수 있으며, 예제에서의 경우와 같이 성립하게 하려면 N 을 다음과 같이 조작하면 됨
  N = N % 4 + 4
  예시에서의 N 의 값은 7이 되며, 이후로는 값이 계속해서 반복되게 되므로, 우리는 7까지의 결과만 알면 된다.
• 위와 같이 하게 되면, 1,000,000,000 이었던 N 의 크기가 한자리로 줄어들게되어, 시간초과가 나지 않으며, 모든 경우에 대해서도 정상적으로 동작하게됨