[Baekjoon] 봄버맨

👀 문제 설명

문제

봄버맨은 크기가 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

 

입력

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

 

출력

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

 

예제 입력 1

6 7 3

.......

...O...

....O..

.......

OO.....

OO.....

 

예제 출력 1

OOO.OOO

OO...OO

OOO...O

..OO.OO

...OOOO

...OOOO

 

✍🏻풀이

BFS를 푸는 방법과 유사하다. dx, dy와 Q를 사용해 인접한 위치를 접근해서 폭탄을 터뜨린다.

먼저 bombQ를 사용해서 폭탄의 위치, 폭탄이 설치된 시간을 넣어주려고 했다. { {1, 0}, 2}

0부터 N초까지 각 시간에 그대로 구현했다. 

1. N이 폭탄을 설치할 수 있는 시간일 때

lastInstallTime을 사용해 마지막 설치한 시간으로부터 2초가 지났을 때, 폭탄을 설치하고, bombQ에 넣어준 후, lastInstallTime을 curTime으로 바꿨다.

 

2. N이 폭탄이 터지는 시간일 때

bombQ가 비어있지 않고, bombQ에 담겨있는 원소의 second값, 즉 폭탄이 설치된 시간이 현재로부터 3초 전이면 폭탄을 터뜨려준다.

이 때, 인접한 네 곳까지 터뜨려주기 위해 dx, dy를 사용했다.

 

아무것도 안하는 시간에는 구현을 할 필요 없으니 구현하지 않았다.

 

하지만 이렇게 하면 문제가 발생한다.

만약, {1, 1}의 위치에 2초에 폭탄을 설치했는데, 3초에 {0, 0}의 폭탄이 터지면서 {1, 1}도 터졌을 때는 bombQ에서 {{1, 1}, 2}라는 원소를 빼줘야 하는데, 큐의 중간에 있는 값에는 접근을 할 수 없으므로 원소를 빼낼 수 없었다.

 

그래서 해결책을 찾아봤는데, 규칙이 있었다.

1. 2초, 4초, 6초, .. 즉 2의 배수인 초에는 모든 위치에 폭탄이 심어지므로, N이 2의 배수일 땐 0으로 이루어진 배열을 출력하면 된다.

2. 홀수초에는 폭탄이 남아 있는 모습을 출력한다. 큐에는 폭탄이 있는 위치만 넣어준다.

 

코드

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

int R, C, N;
char a[201][201];
queue<pair<int, int>> bombQ; // 폭탄의 위치, 폭탄이 설치된 시간이 들어있는 큐 { {1, 0}, 2 }
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

void input() {
    cin >> R >> C >> N;
    for (int i = 0; i < R; i++) {
        string str = "";
        
        cin >> str;
        for (int j = 0; j < C; j++) {
            a[i][j] = str[j];
        }
    }
}

void output() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << a[i][j];
        }
        cout << endl;
    }
}

void queueing() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (a[i][j] == 'O')
                bombQ.push({ i, j });
        }
    }
}

void installBomb() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (a[i][j] != 'O') {
                a[i][j] = 'O';
            }
        }
    }
}

void boom() {
    while (!bombQ.empty()) {
        int bombX = bombQ.front().first;
        int bombY = bombQ.front().second;
        bombQ.pop();
        
        a[bombX][bombY] = '.';
        for (int i = 0; i < 4; i++) {
            int nextX = bombX + dx[i];
            int nextY = bombY + dy[i];
            
            if (nextX < 0 || nextX >= R || nextY < 0 || nextY >= C)
                continue;
            
            a[nextX][nextY] = '.';
        }
    }
}

void solve() {
    for (int curTime = 0; curTime < N; ) {
        queueing();
        curTime++;
        
        if (curTime == N)
            return;
        
        installBomb();
        curTime++;
        
        if (curTime == N)
            return;
        
        boom();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 입력받기
    input();
    
    // N이 짝수일 경우, 모든 값을 O으로 출력하고 return한다
    if (N % 2 == 0) {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                cout << 'O';
            }
            cout << endl;
        }
        
        return 0;
    }
    else {
        solve();
        
        // output
        output();
    }
    
    
    return 0;
}