백준 16916 봄버맨 2 (Java)

1. 문제 링크

16919번: 봄버맨 2

 

2. 문제 및 입출력예제

 

3. 문제 풀이

규칙이 있는 문제이다. (N이 1인 경우를 제외하고는)

4의 배수로 규칙이 발견되는데 N 나누기 4의 나머지에 4를 더한 값이 N이 된다.

N이 되기 전까지 폭탄을 설치하고 시간 체크하고

폭발하는 폭탄을 전부 큐에 넣어두고 시간을 체크한다.

 

여기서 폭탄을 큐에 넣는 이유는 폭탄이 모두 동시에 폭발하기 때문이다.

폭발은 큐에 넣은 것들을 하나씩 빼면서 방문 여부에 체크를 해준다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
	static int R, C, N, map[][];
	static Queue<int[]> queue;
	static boolean[][] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] split = br.readLine().split(" ");
		R = Integer.parseInt(split[0]);
		C = Integer.parseInt(split[1]);
		N = Integer.parseInt(split[2]);  
		
		map = new int[R][C];
		for(int i=0;i<R;i++) {
			String str = br.readLine();
			for(int j=0;j<C;j++) {
				if(str.charAt(j) == 'O') {
					map[i][j] = 1;
				}
				else {
					map[i][j] = 0;
				}
			}
		}
		
		if(N==1) {
			for(int i=0;i<R;i++) {
				for(int j=0;j<C;j++) {
					if(map[i][j] == 1) {
						sb.append('O');
					}
					else {
						sb.append('.');
					}
				}
				sb.append("\n");
			}
		}
		else if(N%2 == 0) {
			for(int i=0;i<R;i++) {
				for(int j=0;j<C;j++) {
					sb.append("O");
				}
				sb.append("\n");
			}
		}
		else {
			N = N % 4 + 4;
			int time = 1;
			while(time < N) {
				for(int i=0;i<R;i++) {
					for(int j=0;j<C;j++) {
						if(map[i][j] == 0) {
							map[i][j] = 2;
						}
					}
				}
				
				time++;
				if(time == N) {
					break;
				}
				queue = new ArrayDeque<>();
				visit = new boolean[R][C];
				for(int i=0;i<R;i++) {
					for(int j=0;j<C;j++) {
						if(map[i][j] == 1) {
							queue.offer(new int[] {i, j});
							visit[i][j] = true;
							bomb(i, j);
						}
					}
				}
				
				while(!queue.isEmpty()) {
					int[] temp = queue.poll();
					map[temp[0]][temp[1]] = 0;
				}
				
				for(int i=0;i<R;i++) {
					for(int j=0;j<C;j++) {
						if(map[i][j] == 2) {
							map[i][j] = 1;
						}
					}
				}
				
				time++;
			}
			
			for(int i=0;i<R;i++) {
				for(int j=0;j<C;j++) {
					if(map[i][j]==0) {
						sb.append(".");
					}
					else {
						sb.append("O");					
					}
				}
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}
	
	private static void bomb(int i, int j) {
		for(int d=0;d<4;d++) {
			int X = i+dx[d];
			int Y = j+dy[d];
			if(X<0 || X>=R || Y<0 || Y>=C || visit[X][Y]) {
				continue;
			}
			queue.offer(new int[] {X, Y});
			visit[X][Y] = true;
		}
	}
}