백준 16918번 : 봄버맨 자바

🧫 문제 분석

 

✔️ 출처

봄버맨 실버 1

 

📖 문제

 

그래프를 써야할것 같은 느낌이 솔솔 느껴진다.

그러나 DFS / BFS 문제는 아니다. 문제에서 '연쇄 반응이 없다' 하였다.

 

문제 실행 단계

0. 초기상태 (폭탄이 미리 심어져있음)

1. 아무것도 안한다.

2. 모든칸에 폭탄 설치

3. 3초전 설치된 폭탄 모두 폭파  

4. 2번 부터 반복 

 

초로 예시를 보면 

 

0초 : 초기 상태

1초 : 아무것도 안함

2초 : 모든 칸에 폭탄 설치

3초 : 3초전에 설치된 폭탄 모두 폭파 (0초 때 설치한 폭탄들)

         - 이때 폭파되지 않은 부분이 다음 초기상태 (0초때 설치한 폭탄들)가 된다.

4초 : 모든 칸에 폭탄 설치

5초 : 3초전 설치된 폭탄 모두 폭파 

 

 

봄버맨 그림 설명

 

0 과 1로 폭탄을 구분하여 설명하자면

먼저 0초때에 초기상태 폭탄이 있고 

• 1초때 아무것도 안한다.
• 2초때 모든 곳에 폭탄을 심는다. (이때 심은 폭탄은 초기상태의 폭탄과 폭팔 시간이 다르므로 1로 설정)
• 3초때 초기에 있던 0 폭탄이 터지면서 좌우상하가 터진다. 
• 4초때 다시 모든 곳에 폭탄을 심는다. (구별을 위해 0으로 설정)
• 5초때 3초 전에 심었던(1 폭탄)이 터진다. 

이를 N초동안 반복하는 것이다.

 

 

 

 

 

 

 

 

내가 생각한 방법

1. 2차원 배열로 그래프를 만든다.

2. 2의 배수 즉, 짝수이면 무조건 2초때의 모든 곳에 폭탄을 심는 타임이다. 그렇기에 2 배수면 모두 0으로 출력한다.

3. 그래프를 탐색하면서 폭탄이 있는 곳이 있고 아직 방문하지 않았다면 상하좌우에 폭탄을 심는다.

4. 그리고 현 그래프를 뒤집어서 폭팔한 후의 상태를 만든다.

 

처음 아무것도 안하기에 N초에서 1을 뺀다.

그리고 폭탄을 심고 터뜨리는 것을 한번에 처리할 것이다.

모든 곳이 폭탄인 경우는 2의 배수말고는 없기에 홀수 초에서 나올 수 없다. 

그렇기에 폭탄을 심고 터뜨리는 것을 한번에 처리해서 하되 N초에서 2초씩 빼면서 반복한다.

 

 

---

🔅 문제 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter 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 nSeconds = Integer.parseInt(st.nextToken());
        
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0 , 0};
        boolean[][] visited = new boolean[R][C];
        char[][] graph = new char[R][C];

		// 격자판 데이터 그래프에 초기화 
        for (int i = 0; i < R; i++) {
            graph[i] = br.readLine().toCharArray();
        }

        // 2의 배수 초에는 항상 모든 폭탄이 가득참
        if (nSeconds % 2 == 0) {
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    bw.write('O');
                }
                bw.write("\n");
                bw.flush();
            }
            bw.close();
            return;
        }

        // 설치 후 무동작이기에 1초를 빼고 시작
        nSeconds--;

        while (nSeconds > 0) {
            
            // 0으로 채우고(1초) + 폭발시키기(1초) 
            nSeconds -= 2;

            // 폭팔한 곳은 0으로 채우기
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {

                    if (graph[i][j] == 'O' && !visited[i][j] ) {
                        visited[i][j] = true;
                        for (int k = 0; k < 4; k++) {
                            int dX = j + dx[k];
                            int dY = i + dy[k];


                            if ((dX >= 0 && dX < C && dY >= 0 && dY < R) && !visited[dY][dX] ) {
                            	// 상하좌우 위치에 있는 폭탄이 기존에 있는 폭탄이라면 건들지 않는다.
                                // 이유 : 방문을 체크하는데 위에서 말한 그 폭탄이 체크되면 그 폭탄에 더이상 방문하지 않아 그 폭탄의 상하좌우는 터지지 않기때문이다.
                                if (graph[dY][dX] != 'O') {
                                    graph[dY][dX] = 'O';
                                    visited[dY][dX] = true;
                                }
                            }
                        }
                    }
                }

            }

            // 폭발 후 상황으로 만듦
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (graph[i][j] == '.') {
                        graph[i][j] = 'O';
                        
                    }else {
                        graph[i][j] = '.';
                    }
                }
            }
            
            visited = new boolean[R][C];
        }
        
        // N초 후 격자판 상태
        for (char[] chars : graph) {
            for (char aChar : chars) {
                bw.write(aChar);
            }
            bw.write("\n");
            bw.flush();
        }

        bw.close();
        
    }

}

 

---

 

'0' 인줄 알고 시간낭비를 엄청했다. 알고보니 숫자 0이 아니라 대문자 O였다;

다음부터는 예시에 있는 문자를 사용해야겠다.

 

 

❗ 오답노트 / 필요한 지식

1. 방문 체크에 대해 항상 고민해야한다. 
2. 확실하게 직접 시뮬레이션을 돌리자. 나 자신이 컴퓨터가 된것처럼