16918_봄버맨

사용 알고리즘: 구현, 시뮬레이션

사용 언어: java

 

package ssafyRoom2_Monthly_Silver_Random_Defense;

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


public class Main {
	static List<int[]> bombs = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		char[][][] maps = new char[3][R][C]; // 짝수일 땐 O으로만 채우니까 제외
		
		for (int i = 0; i < R; i++) {
			String s = br.readLine();
			for (int j = 0; j < C; j++) {
				maps[0][i][j] = s.charAt(j);
				if(maps[0][i][j] == 'O') {
					bombs.add(new int[] {i, j});
				}
			}
		}
		
		bomb(maps, R, C);
		
		if(N <= 1) {
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					System.out.print(maps[0][i][j]);
				}
				System.out.println();
			}
		} else if(N % 2 == 0) {
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					System.out.print('O');
				}
				System.out.println();
			}
		} else if(N % 4 == 3) { //3 7 11 ...
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					System.out.print(maps[1][i][j]);
				}
				System.out.println();
			}
		} else {
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					System.out.print(maps[2][i][j]);
				}
				System.out.println();
			}
		}
	}

	private static void bomb(char[][][] maps, int R, int C) {
		char[][] tmap = new char[R][C];
		for (int i = 0; i < R; i++) {
			Arrays.fill(tmap[i], 'O');
		}
		
		int[] dx = {-1,1,0,0};
		int[] dy = {0,0,-1,1};
		
		for(int[] b : bombs) {
			tmap[b[0]][b[1]] = '.';
			for (int d = 0; d < 4; d++) {
				int nx = b[0] + dx[d];
				int ny = b[1] + dy[d];
				
				if(nx>=0&&nx<R && ny>=0&&ny<C) {
					tmap[nx][ny] = '.';
				}
			}
		}
		
		bombs.clear();
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				maps[1][i][j] = tmap[i][j];
				if(tmap[i][j] == 'O') {
					bombs.add(new int[] {i, j});
				}
			}
		}
		
		for (int i = 0; i < R; i++) {
			Arrays.fill(tmap[i], 'O');
		}
		
		for(int[] b : bombs) {
			tmap[b[0]][b[1]] = '.';
			for (int d = 0; d < 4; d++) {
				int nx = b[0] + dx[d];
				int ny = b[1] + dy[d];
				
				if(nx>=0&&nx<R && ny>=0&&ny<C) {
					tmap[nx][ny] = '.';
				}
			}
		}
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				maps[2][i][j] = tmap[i][j];
				if(tmap[i][j] == 'O') {
					bombs.add(new int[] {i, j});
				}
			}
		}
	}

}

 

나올 수 있는 맵의 모양은 반복된다.

그러므로 나올 수 있는 네 가지 경우의 수를 미리 구해놓고

N번째에 어떤 패턴의 맵이 나올지 출력해야 한다.

 

만약 빡구현을 한다면 시간 초과가 난다.......

 

나올 수 있는 네 가지 수

1. 초기에 입력 받은 맵(N=0이거나 1일 때)

2. 맵 전체가 'O'으로 채워진 맵(N이 2이상 짝수일 때)

3. N=3일 때 맵(N이 2이상이고 N%4가 3일 때)

4. N==5일 때 맵(나머지 경우)