[Baekjoon/Java] 16918번 봄버맨

문제

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

• 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
• 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
• 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
• 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
• 3과 4를 반복한다.

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

예를 들어, 초기 상태가 아래와 같은 경우를 보자.

...
.O.
...

1초가 지난 후에는 아무 일도 벌어지지 않기 때문에, 위와 같다고 볼 수 있다. 1초가 더 흐른 후에 격자판의 상태는 아래와 같아진다.

OOO
OOO
OOO

1초가 지난 후엔 가운데에 있는 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.

O.O
...
O.O

 

 

입력

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

 

출력

총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

 

문제 풀이

 

첫번째 풀이 - 틀렸습니다 * 5

2시간에 걸쳐 풀었던 문제다. 문제를 제대로 이해하지 못 했기 때문이라고 생각한다.

나는 일단 입력 값을 문자열 배열에 따로 저장해두지 않고 시간을 카운트할 배열만 만들었다.

그리고 N번 만큼 반복하면서 홀수라면 그리고 폭탄이 없다면 카운트를 +1 해줬다.

그리고 짝수라면 반복문을 돌면서 카운트를 +1 해주고 만약 q가 true이면서 3초가 지났다면 queue에 넣고 상하좌우를 방문하며 폭탄을 터트렸다.

여기서 q라는 boolean 변수를 만든 이유는 아무때나 queue에 입력할 수 없기 때문에 만들었던 것 같은데 지금 생각하면 왜 만들었나 싶은 이상한 코드였다....

 

코드에서 잘못된 부분들이 여러개 있는데 일단 나는 처음엔 0 ~ N-1번까지 반복을 진행했다. 하지만 문제에서는 처음 1초 동안은 아무 것도 하지 않는다고 했다. 하지만 내 코드에서는 처음부터 카운트를 +1 했다.

 

그리고 내가 이해했던 문제는 3초가 됐을 때 폭탄을 터트리고 그 다음 번째에서도 만약 3초가 된 폭탄이 있다면 터트리는 것으로 이해했다. 하지만 문제는 3초가 됐을 때 폭탄을 터트리고 그 다음 번째에서는 비워져 있는 부분에 폭탄을 설치하는 것이었고 그 다음 번째에서 폭탄을 터트리는 것이었다.

 

또 잘못한 부분은 위에 말했던 왜 만들었는지 의문인 q ...

 

맞았습니다를 도출하기까지는 오래걸렸지만 내 코드의 문제는 크게 3개였던 것 같다.

 

최종 풀이

0 ~ N-1번까지 반복하는 것이 아닌 2번째부터 N까지 반복하도록 수정했고

만약 짝수라면 카운트를 +1 하고 홀수라면 그리고 현재 위치의 cnt가 2 이상이라면 queue에 넣었다.

왜 2 이상일 때만이라고 했냐면 그냥 0이 아닐 때라고 할 경우엔 이전 단계에서 폭탄을 설치했다면 그 폭탄은 1일텐데 이 폭탄은 3초가 지나지 않았기 때문에 터트릴 수 없기 때문이다.

그리고 queue에 담은 좌표들을 기준으로 상하좌우를 탐색하며 폭탄을 터트려줬다.

 

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int R;
	static int C;
	static int N;
	static char[][] ans;
	static int[][] cnt;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		R = sc.nextInt();
		C = sc.nextInt();
		N = sc.nextInt();
		ans = new char[R][C];
		cnt = new int[R][C];
		
		for(int i=0; i<R; i++) {
			String s = sc.next();
			for(int j=0; j<C; j++) {
				if(s.charAt(j) == 'O') {
					cnt[i][j] = 1;
				}
			}
		}
		boom();
		
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				if(cnt[i][j] == 0) {
					ans[i][j] = '.';
				}else {
					ans[i][j] = 'O';
				}
			}
		}
		
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				sb.append(ans[i][j]);
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
	
	private static void boom() {
		Queue<int[]> queue = new LinkedList<int[]>();
		
		for(int i=2; i<=N; i++) {
			if(i % 2 == 0) {
				for(int j=0; j<R; j++) {
					for(int k=0; k<C; k++) {
						cnt[j][k]++;								
					}
				}
			}else if(i % 2 != 0){
				for(int j=0; j<R; j++) {
					for(int k=0; k<C; k++) {
						if(cnt[j][k] >=2) {
							queue.add(new int[] {j,k});
						}
					}
				}
				
				while(!queue.isEmpty()) {
					int[] tmp = queue.remove();
					cnt[tmp[0]][tmp[1]] = 0;
					for(int d=0; d<4; d++) {
						int nx = dx[d] +tmp[0];
						int ny = dy[d] + tmp[1];
						if(0<=nx && nx<R && 0<=ny && ny<C) {
							cnt[nx][ny] = 0;
						}
					}
				}
			}
		}
		
	}
}

 

새롭게 알게 된 점 & 느낀점

솔직히 이렇게 오래 걸릴 문제라고 생각하진 않았다. 근데 문제를 잘못 이해하는 순간 코드는 점점 산으로 갔고 질문 게시판에서도 많은 반례가 없어서 더 어려운 느낌이었다. bfs 문제인 줄 알았는데 완전 bfs 문제는 아니었고 구현, 시뮬레이션에 더 가까운 문제였다. 이런 시뮬레이션 문제일 수록 문제에서 요구하는 것을 더 잘 봐야하는데 앞으로 문제를 완전히 이해하고 코드를 짜는 습관을 더 들이도록 해야겠다.

 

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

16918번: 봄버맨