[BOJ] 16918. 봄버맨(BFS, 시뮬레이션)

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

봄버맨의 행동을 구현해보자.

행동을 간추려보면 단순하다.

1. 폭탄이 설치되지 않은 영역에 폭탄 설치

2. 전에 설치된 폭탄이 모두 폭발

얼마나 효율적으로 구현하느냐가 중요할 것 같다.

#. Code

처음 구현한 방법은 상당히 단순하며 비효율적이다.. 하핳

배열을 Copy하는 부분과 매초 동작은 수행하는 부분에서 

실행 시간이 많이 소요된다.

자세한 설명은 최적화된 코드에서..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ16918 {
 
    static int R, C, N;
    static char map[][][];
    static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};
    
    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[2][R][C];
        for (int i = 0; i < R; i++) {
            map[0][i] = br.readLine().toCharArray();
        }
        
        int idx = 0;
        // N이 1이 아닐 경우 동작
        if(N != 1) idx = process();
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                sb.append(map[idx][i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
 
    private static int process() {
 
        int idx = 1, rr = 0, cc = 0, time = 1;
        
        while(true) {
            
            copy(map[idx^1], map[idx]);
            
            // 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if(map[idx][i][j] == 'O') continue;
                    map[idx][i][j] = 'O';
                }
            }
            if(++time == N) return idx;
            
            // 전에 설치된 폭탄이 모두 폭발
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    if(map[idx^1][r][c] == '.') continue; 
                    // 전에 설치된 폭탄일 경우 폭탄이 있던 칸이 파괴, 
                    map[idx][r][c] = '.';
                    // 인접한 네 칸도 함께 파괴
                    for (int d = 0; d < 4; d++) {
                        rr = r + dr[d];
                        cc = c + dc[d];
                        if(rr < 0 || cc < 0 || rr >= R || cc >= C) continue;
                        map[idx][rr][cc] = '.';
                    }
                }
            }
            if(++time == N) return idx;
            
            System.out.println("============TIme" + time);
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    System.out.print(map[idx][i][j]);
                }System.out.println();
            }
            
            idx ^= 1;
        }
    }
 
    private static void copy(char[][] src, char[][] dst) {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                dst[i][j] = src[i][j];
            }
        }
    }
}

#. Code_v2

첫 번째 코드에서 너무 비효율적이었다..

최적화 방법에는 

1. 시뮬레이션을 해보면 짝수 초에는 무조건 모든 칸에 폭탄이 채워진다.

   그러므로 더이상 진행할 필요가 없다. 그냥 폭탄이 다 채워진 상태를 출력해주자. (line 23~32)

2. 약간 허무할 수 있는데.. 1초~4초까지의 상태가 계속해서 반복된다.

   즉, 1초~4초의 상태를 알면 모든 경우를 단순하게 확인할 수 있다.

     짝수 초일 경우를 예외처리해 주었으므로 홀수 초일 경우를 생각해보자.

   2초에 걸쳐서 두 동작이 있지만(폭탄이 설치되지 않은 영역에 폭탄 설치, 전에 설치된 폭탄이 모두 폭발)

   짝수일 경우는 체크할 필요가 없으므로, 생각하기 쉽게 두 동장을 묶고 N/2초만큼 동작시키면 된다. (line 40)

   단, N/2의 결과가 4보다 클 경우, 1초~4초까지의 상태가 계속해서 반복되므로 

   (N / 2 - 4) % 2 + 4 만큼만 동작시켜주어도 된다. (line 39)

   

3. 나는 처음에 단순하게 배열을 복사하는 방법을 선택했는데

   사실 빈칸은 폭탄으로, 폭탄은 빈칸으로 바꿔주기만 하면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ16918_v2 {       static int R, C, N;     static char map[][][];     static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         StringBuilder sb = new StringBuilder();                  R = Integer.parseInt(st.nextToken());         C = Integer.parseInt(st.nextToken());         N = Integer.parseInt(st.nextToken());                  // 짝수일 경우 무조건 폭탄이 모두 설치된 상태         if(N % 2 == 0) {             for (int i = 0; i < R; i++) {                 for (int j = 0; j < C; j++) {                     sb.append('O');                 }                 sb.append("\n");             }             System.out.println(sb);             return;         }                  map = new char[2][R][C];         for (int i = 0; i < R; i++) {             map[0][i] = br.readLine().toCharArray();         }                  if(N / 2 > 4) N = (N / 2 - 4) % 2 + 4;         else N /= 2;                  int idx = process();         for (int i = 0; i < R; i++) {             for (int j = 0; j < C; j++) {                 sb.append(map[idx][i][j]);             }             sb.append("\n");         }         System.out.println(sb);     }       private static int process() {           int cur = 0, nxt = 1, time = 0;                  while(time < N) {                          ++time;             // 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치             for (int i = 0; i < R; i++) {                 for (int j = 0; j < C; j++) {                     if(map[cur][i][j] == '.') {                         map[nxt][i][j] = 'O';                     } else {                         // 전에 설치된 폭탄일 경우 폭탄이 있던 칸이 파괴,                          map[nxt][i][j] = '.';                     }                 }             }                          // 전에 설치된 폭탄이 모두 폭발             for (int r = 0; r < R; r++) {                 for (int c = 0; c < C; c++) {                     if(map[cur][r][c] == '.') continue;                      // 인접한 네 칸도 함께 파괴                     for (int d = 0; d < 4; d++) {                         int rr = r + dr[d];                         int cc = c + dc[d];                         if(rr < 0 || cc < 0 || rr >= R || cc >= C) continue;                         map[nxt][rr][cc] = '.';                     }                 }             }                          cur ^= 1;             nxt ^= 1;         }                  return cur;     }   } Colored by Color Scripter

cs