문제

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

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

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

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

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

---

입력

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

출력

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

---

처음에 시도했던 방법

1초 뒤에 곧 폭발할 예정인 폭탄들은 파란색으로 나타냈다. 그림을 보면, (1, 5, 9, ...), (2, 6, 10, ...), (3, 7, 11, ...), (4, 8, 12, ...) 등 4초 간격으로 동일한 패턴을 보인다는 걸 알 수 있다.

4n + 1 -> 초기
4n + 2 -> 새로 설치
4n + 3 -> 폭발
4n + 4 -> 새로 설치
(n은 0 이상의 정수)

그래서 n을 4로 나눈 나머지 값에 따라 격자판 상태를 분류하여 출력해봐야겠다고 생각했다. 단, 4n + 2, 4n + 4는 모든 칸에 폭탄이 설치된 상태로 동일하게 출력했다.

#include <iostream>
using namespace std;

int r, c, n; // 1 ≤ R, C, N ≤ 200

char input[201][201]; // 초기 상태 입력 
char temp[201][201]; // 초기 상태 임시 저장
char all[201][201]; // 모든 칸에 폭탄이 설치된 상태 
char bomb[201][201]; // 폭탄이 터진 상태 

// 2차원 배열 출력 
void print2DArray(char arr[][201]){
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cout <<  arr[i][j];
		}
		cout << "\n";
	}
}

int main()
{
	cin >> r >> c >> n;

	// 초기 상태 입력 받기 
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cin >> input[i][j];
		}
	}

	// 초기 상태 임시 저장해두기
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			temp[i][j] = input[i][j];
		}
	}

	// 폭탄이 모두 설치된 상태
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			all[i][j] = 'O';
			bomb[i][j] = 'O';
		}
	}

	// 초기에 설치했던 폭탄들이 터진 상태 한번만 구해보자.
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			if(input[i][j] == 'O'){
				bomb[i][j] = '.';

				if(i > 0){
					bomb[i - 1][j] = '.'; // 상
				}
				
				if(i < r - 1){
					bomb[i + 1][j] = '.'; // 하
				}

				if(j > 0){
					bomb[i][j - 1] = '.'; // 좌
				}

				if(j < c - 1){
					bomb[i][j + 1] = '.'; // 우
				}
			}
		}
	}

	if(n == 0){
		print2DArray(temp); // 초기 상태 출력
		return 0;
	}
	
	// 4로 나눈 나머지 값에 따라 출력
	switch(n % 4){
		case 1: // 초기 상태 
			print2DArray(temp);
			break;
		case 0:
		case 2: // 모든 칸에 설치된 상태
			print2DArray(all);
			break;
		case 3: // 폭탄이 터진 상태 
			print2DArray(bomb);
			break;
	}
	
	return 0;
}

예제 입력에 대한 출력은 제대로 나오는데, 알고리즘이 틀려서 오답인 거 같다.

다른 풀이

참고: https://yabmoons.tistory.com/198

0초 = 폭탄을 심는다.(초기상태)
1초 = 아무것도 하지 않는다.

2초 = 폭탄이 없는 위치에 폭탄을 설치한다.
3초 = 0초에 심은 폭탄이 터진다.

4초 = 폭탄이 없는 위치에 폭탄을 설치한다.
5초 = 2초에 심은 폭탄이 터진다.

6초 = 폭탄이 없는 위치에 폭탄을 설치한다.
7초 = 4초에 심은 폭탄이 터진다.
...

2초부터 보면, 짝수 초에는 폭탄을 설치하고, 홀수 초에는 폭탄이 터지는 패턴이 반복된다는 걸 알 수 있다. 즉, 우리는 N초까지, 위의 규칙을 반복하기만 한다면 정답을 구할 수 있다.

사실, 폭탄을 설치하는 것은 문제되지 않지만, 어느 폭탄이 몇 초에 터지는지를 우리는 저장해놓고 알아내야 한다.

이를 위해 bombTime[][] 이라는 2차원 배열을 하나 더 만들어 줄 수 있다. bombTime[a][b] = c는 (a, b)에 있는 폭탄은 c초 뒤에 터진다는 것을 의미한다.

즉, 폭탄이 터지는 홀수 초마다 맵 전체를 돌면서, 현재 시간과 bombTime[][]의 값이 같다면, 그 폭탄을 터뜨리고 폭탄이 없는 상태로 바꿔주면 된다. 폭탄을 없앰과 동시에 bombTime[][]의 값도 다시 0으로 초기화 시켜줘야 된다는 것도 잊지 말자.

#include <iostream>
#define MAX 200
using namespace std;

int r, c, n; // 1 ≤ R, C, N ≤ 200
int bombTime[MAX][MAX];
char mat[MAX][MAX];

// 상하좌우
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

// 짝수 초일 때 폭탄 설치 
void installBomb(int time){
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			if(mat[i][j] == 'O') 
				continue;
				
			// 폭탄이 설치되지 않은 곳에만 새로 설치
			mat[i][j] = 'O';

			// 현재 시간으로부터 3초 뒤에 터진다. (2->5, 4->7)
			bombTime[i][j] = time + 3; 
		}
	}
}

// 홀수 초일 때 폭탄 파괴 
void deleteBomb(int time){
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			if(bombTime[i][j] == time){
				mat[i][j] = '.'; // 자신의 칸 파괴
				
				// 상하좌우 파괴 
				for(int k = 0; k < 4; k++){
					int nx = i + dx[k];
					int ny = j + dy[k];

					if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
					if(mat[nx][ny] == '.') continue;

					mat[nx][ny] = '.';
				}

				// 현재 칸의 폭탄 터지는 시간 업데이트  
				bombTime[i][j] = 0; 
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
	
	cin >> r >> c >> n;

	// 초기 상태 입력 받기 
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cin >> mat[i][j];

			// (i, j)에  있는 폭탄이 3초 뒤에 터진다.
			if(mat[i][j] == 'O'){
				bombTime[i][j] = 3;
			}
		}
	}

	int time = 2; 
	while(1){
		// n초가 지났을 때 루프 종료 
		if(time == n + 1) break; 

		// 짝수 초일 때 폭탄 설치 
		if(time % 2 == 0){
			installBomb(time);
		}else{ 
			// 홀수 초일 때 폭탄 파괴 
			deleteBomb(time);
		}

		time++;
	}

	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cout << mat[i][j];
		}
		cout << "\n";
	}
	
	return 0;
}