[백준] 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

 

 

풀이

---

문제에서 원하는대로 구현을 하면 되는 문제였다.

 

폭탄의 위치를 저장할 2차원배열과, 각각의 폭탄이 터지는 시간을 저장할 2차원 배열을 이용해서 풀었다.

 

폭탄이 터질경우는 Queue를 이용하여 위치를 저장 한 뒤 (i+1, j), (i-1, j), (i, j+1), (i, j-1) 위치를 . 으로 바꿔주었다.

 

짝수 시간에서는 폭탄을 놓아야 하므로 setBomb 메서드를 이용하여 해당 시간에 빈칸은 폭탄을 놓은 뒤 시간 + 3을 저장했다.

 

홀수 시간에는 폭탄이 터지므로 해당 시간에 터지는 폭탄을 changeBomb() 메서드를 이용하여 폭탄을 제거하였다.

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static String[][] board;
	static int[][] time;
	static int[][] move = { {1,0}, {-1,0}, {0,-1}, {0,1} };
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int sec = Integer.parseInt(st.nextToken());
		
		board = new String[r][c];
		time = new int[r][c];
		for(int i = 0 ; i < r ; i++) {
			String[] line = bufferedReader.readLine().split("");
			for(int j = 0 ; j < c ; j++) {
				board[i][j] = line[j];
				if(board[i][j].equals("O")) {
					time[i][j] = 3;
				}
			}
		}
	
		for(int i = 1 ; i <= sec ; i++) {
			if(i % 2 == 0) {
				setBomb(r, c, i);
			}
			else {
				changeBomb(r, c, i);
			}
		}
		
		printBomb(r, c);
		System.out.println(sb);
	}
	
	static class Point{
		int r, c;
		
		Point(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	
	static void setBomb(int r, int c, int t) {
		for(int i = 0 ; i < r ; i++) {
			for(int j = 0 ; j < c ; j++) {
				if(board[i][j].equals(".")) {
					board[i][j] = "O";
					time[i][j] = t + 3;
				}
			}
		}
	}
	
	static void changeBomb(int r, int c, int t) {
		
		Queue<Point> queue = new LinkedList<>();
		
		for(int i = 0 ; i < r ; i++) {
			for(int j = 0 ; j < c ; j++) {
				if(board[i][j].equals("O") && time[i][j] == t) {
					queue.add(new Point(i, j));
				}
			}
		}
		
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			
			board[now.r][now.c] = ".";
			time[now.r][now.c] = 0; 
			
			for(int i = 0; i < 4 ; i++) {
				int nr = now.r + move[i][0];
				int nc = now.c + move[i][1];
				
				if(nr < 0 || nr >= r || nc < 0 || nc >= c) { continue; }
				
				if(board[nr][nc].equals(".")) { continue; }
				
				board[nr][nc] = ".";
				time[nr][nc] = 0;
			}
		}
		
	}
	
	static void printBomb(int r, int c) {
		
		for(int i = 0 ; i < r ; i++) {
			for(int j = 0 ; j < c ; j++) {
				sb.append(board[i][j]);
			}
			sb.append("\n");
		}
	}
}