[ baekjoon ] #16918 봄버맨

백준 #16918 봄버맨

문제 요약

---

• R×C 크기의 격자판, 각 칸은 비어있거나 폭탄이 들어있다.
• 폭탄이 있는 칸은 3초가 지난 후 폭발한다.
  → 폭탄이 있던 칸은 파괴되어 빈칸이 된다.
  → 인접한 네 칸도 함께 파괴된다.
• 폭탄이 폭발했을 때 인접한 칸에 폭탄이 있었다면 폭발 없이 파괴된다.
• 봄버맨의 행동
  ① 가장 처음에 일부 칸에 폭탄을 설치한다. 모든 폭탄이 설치된 시간은 같다.
  ② 다음 1초 동안 아무것도 하지 않는다.
  ③ 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다.
  (모두 동시에 설치했다고 가정)
  ④ 1초가 지난 후 3초 전에 설치된 폭탄이 모두 폭발한다.
  ⑤ ③, ④를 반복한다.

💡Idea(BFS)

1. 폭탄의 유무를 어떻게 판단할까?
   → check 배열의 값으로 폭탄이 있는지 없는지 판단하자.
2. 기존에 있던 폭탄과 폭탄이 없는 곳에 설치한 폭탄을 어떻게 구분할까?
   → 기존의 폭탄을 quque 에 넣고 파괴한 후 남은 폭탄을 다시 queue에 넣어주자 !
   → 1초까지는 처음의 상태와 같고 2의 배수일 때는 모든 칸에 폭탄이 존재하며 2의 배수가 아닐 때는 기존의 폭탄을 파괴시키자.

[ SourceCode ]

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

#define endl "\n"

int R, C, N; // 격자판 행, 열, 목표 시간

char map[200][200];
int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // 상하좌우
int check[200][200];

void bfs(queue <pair<int, int>> bomb) {
    while (!bomb.empty()) {
        pair <int, int> now = bomb.front();
        bomb.pop();
        int x = now.first;
        int y = now.second;

        map[x][y] = '.'; // 폭탄 파괴
        check[x][y] = 0; // 폭탄 없음

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            map[nx][ny] = '.';
            check[nx][ny] = 0;
        }
    }
}

int main() {
    cin >> R >> C >> N;

    queue <pair<int, int>> bomb; // 폭탄
    for (int i = 0; i < R; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < C; j++) {
            map[i][j] = str[j];
            if (map[i][j] == 'O') {
                bomb.push({ i, j });
                check[i][j] = 1;
            }
        }
    }

    for (int i = 2; i <= N; i++) {
        if (i % 2 == 0) { // 모두 폭탄
            for (int j = 0; j < R; j++) {
                for (int k = 0; k < C; k++) {
                    map[j][k] = 'O';
                    check[j][k] = 1;
                }
            }
        }

        else { // 폭탄 파괴
            bfs(bomb);
            bomb = queue<pair<int, int>>(); // 초기화
            for (int j = 0; j < R; j++) {
                for (int k = 0; k < C; k++) {
                    if (check[j][k]) {
                        bomb.push({ j, k });
                    }
                }
            }
        }
    }
   
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << map[i][j];
        }
        cout << endl;
    }

    return 0;
}

Feedback

---

1. 처음에 정신없이 check 배열을 char로 만듦,,
   → 실수 줄이기 !!!
2. queue 초기화 방법을 몰랐음.

Remind

---

• bomb = queue<pair<int, int>>();
  → 이런식으로 재생성함으로써 초기화 가능 !!