봄버맨
문제 해석
조건에 맞게 폭탄을 설치 및 폭발시키는 작업을 N초동안 진행한 뒤의 상태를 구하는 문제입니다.
봄버맨은 다음과 같이 행동합니다.
- 가장 처음에 일부칸에 폭탄을 설치해 놓습니다.(초기입력)
- 다음 1초동안 아무것도 하지 않습니다.
- 다음 1초동안 폭탄이 설치되어있지 않은 모든칸에 폭탄을 설치합니다.
- 1초가 지난 후에 3초전에 설치된 폭탄이 모두 폭발합니다.
- 3과 4를 반복합니다.
폭탄이 폭발했을 때 인접한 상하좌우 칸도 함께 파괴되며, 인접하는 칸에 폭탄이 있는 경우 연쇄반응이 일어나지 않습니다.
설계(10)
조건에 맞게 구현하면 되는 구현문제입니다.
처음 설치된 폭탄의 위치에 1 값을 저장해놓습니다.
이후, 나머지 빈칸에 2를 채웁니다.
시간을 증가시키면서 폭탄 폭발과 채워넣는 과정을 반복합니다.
폭탄 폭발시, idx라는 변수를 이용하여 1과 2의 폭탄이 번갈아가면서 터지도록 설정해줍니다.
총 시간복잡도는 최대 N번 반복하면서 폭탄 설치 or 폭발 (O(RxC))을 진행해야하기 때문에 O(RxCxN)으로 시간안에 구현이 가능합니다.
그러나, 각 시간의 상태표를 보면 알겠지만 1번폭탄 터진 상태, 모두 채워진 상태, 2번폭탄 터진 상태, 모두 채워진 상태. 이 네가지 상태가 반복되는 것을 알 수 있습니다(N>=3).
따라서 N을 3 감소시켜준 후, 모듈로 4를 하여 최대 4번만 반복하면 원하는 상태를 구할 수 있게 됩니다. => O(4xRxC) = O(RxC)
구현(30)
코드
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 201
int arr[MAXN][MAXN];
int copy_arr[MAXN][MAXN];
int R, C, N;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C >> N;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
char tmp;
cin >> tmp;
if (tmp == 'O') arr[i][j] = 1;
}
}
if (N >= 2) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (arr[i][j] == 0) arr[i][j] = 2;
}
}
}
if (N > 2) {
N -= 3;
N = N % 4;
int time = 0;
int idx = 1;
while (time <= N) {
memcpy(copy_arr, arr, sizeof(arr));
// 폭발
if (time % 2==0) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (copy_arr[i][j] == idx) {
arr[i][j] = 0;
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;
arr[nx][ny] = 0;
}
}
}
}
idx = 3 - idx;
}
// 채우기
else {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (!arr[i][j]) {
arr[i][j] = 3-idx;
}
}
}
}
time++;
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
char tmp;
if (arr[i][j]) tmp = 'O';
else tmp = '.';
printf("%c", tmp);
}
printf("\n");
}
return 0;
}
디버깅
폭탄폭발을 구현하는 부분에서 폭발해야하는 부분을 arr로 바로 갱신시키는 실수를 하였습니다.
그러나, 지문에서 폭발이 동시에 폭발을 해야한다고 명시가 안되어있고, 인접한 칸에 폭탄이 있는 경우 인접한 폭탄은 폭발 없이 파괴된다라는 지문의 혼동으로 인해 논리적 오류를 범한 것 같습니다.
copy_arr라는 배열로 배열을 복사하여 다른 폭탄들도 모두 터지도록 변경하였습니다.
제출결과
0 ms
마무리
단순한 구현문제였지만, 예외처리를(N=1or N=2인 경우)생각해야하는 문제였습니다.