[C++] 백준/BOJ - 16918 : 봄버맨

문제 이해 단계

위 문제는 힌트를 보면 이해하기가 더 쉽다.

.......
...O...
....O..
.......
OO.....
OO.....

<초기 상태, 1초 후>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

<2초 후>

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

<3초 후>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

<4초 후>

.......
...O...
....O..
.......
OO.....
OO.....

<5초 후>

 이를 요약한다면

0초 - 일부 칸 폭탄 설치(초기상태)
1초 - 행동 X
2초 - 폭탄 없는 칸에 전부 폭탄 설치
3초 - 행동 X(0초 때 설치해 뒀던 폭탄 터짐)
이후 2초, 3초 행동 반복

이 말은 폭탄이 터져 그 주변이 비게 되면, 1초 후 그 빈자리를 폭탄으로 다시 채운다.
이 과정을 계속 반복한다고 보면 된다.

즉, 짝수 초 일 때는 모든 칸에 폭탄이 설치되어 있다.
홀수 초 일 때는 전에 설치되어 있던 폭탄이 터진 모양을 계산하면 되는 것이다.

 

---

문제 접근 단계

폭탄이 터지면, 그 폭탄과 + 모양으로 인접한 4칸이 파괴된다.

다행히 파괴된 자리에 폭탄이 있더라도
폭탄이 터지지 않고 그냥 파괴됨으로 연쇄작용은 없다.

2차원 배열에서 폭탄의 위치를 찾고, 새로운 폭탄을 생성하는 일을 해야 한다.
따라서 전형적으로 BFS 혹은 DFS로 풀어야 하는 문제임을 인지했다.

큐 안에 폭탄의 위치를 저장해 두는 것이 더 편할 것 같아서
큐를 사용하는 BFS를 쓰기로 했다.

일단 시간 N이 홀수일 때만 BFS를 돌려주면 된다.
왜냐하면 짝수일 때는 항상 모든 배열이 O을 호출하기 때문에 따로 계산이 필요 없기 때문이다.

구현 방식은 실제로 시간이 N초가 될 때까지 해당 작업을 반복하는 것이었다.
1초부터 시간을 2초씩 더해가며 폭탄이 터지고 빈자리를 채우는 과정을 반복한다.

이후 시간이 N초가 되면 그 모양을 출력하는 것으로 끝낸다.

 

---

문제 구현 단계

char input[201][201];
int R, C;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

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

	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++) {
			cin >> input[i][j];
		}

들어오는 입력값 배열 input, R, C
+범위로 작업을 하기 위한 배열 dx [], dy []를 선언해 줬다.

if (N % 2 == 0) {
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++)
				cout << 'O';
			cout << "\n";
		}
		return 0;
	}
	else {
		int cnt = 1;
		while (cnt < N) {
			queue<pair<int, int>> q;
			for (int i = 1; i <= R; i++)
				for (int j = 1;j <= C; j++) {
					if (input[i][j] == 'O') q.push(make_pair(i, j));
				}
			for (int i = 1; i <= R; i++)
				for (int j = 1; j <= C; j++) input[i][j] = 'O';

시간 N이 짝수 일 때는 무조건 O이 출력하도록 해주고,
홀수일 때만 BFS 작업을 시작한다.

우선 현재 시간을 나타내는 cnt를 1로 초기화,
이후 input에서 폭탄을 찾아 그 위치를 모두 큐에 저장한다.

이후, 2초의 작업(폭탄을 모두 채우는 작업)을 해준다.

while (!q.empty()) {
				int x = q.front().first;
				int y = q.front().second;
				q.pop();

				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
					input[nx][ny] = '.';
				}
				input[x][y] = '.';
			}
			cnt += 2;

이후 BFS를 시작한다.

큐가 빌 때까지 값의 왼쪽 오른쪽 위아래를 확인해서 배열 범위 안에 들어와 있고,
왼쪽 오른쪽 위아래와 자기 자신을 '.'으로 바꾼다.

이후 시간을 2초 뒤로 갱신시켜 준다. 
이 작업을 while(cnt < N) 일 때까지 반복한다.

cnt = N 일 때는 반복하면 안 되는 이유는
이미 cnt - 2 = N 일 때, cnt = N 초일 때의 작업을 한 것이기 때문이다.

cnt = N 일 때 한번 더 반복을 하면
N+2초 때의 작업을 한 게 된 것이기 때문에 틀리게 된다.

아래는 전체 코드를 올려놓고 끝내겠다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool c[201][201] = { false };
char input[201][201];
int R, C;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

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

	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++) {
			cin >> input[i][j];
		}


	if (N % 2 == 0) {
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++)
				cout << 'O';
			cout << "\n";
		}
		return 0;
	}
	else {
		int cnt = 1;
		while (cnt < N) {
			queue<pair<int, int>> q;
			for (int i = 1; i <= R; i++)
				for (int j = 1;j <= C; j++) {
					if (input[i][j] == 'O') q.push(make_pair(i, j));
				}
			for (int i = 1; i <= R; i++)
				for (int j = 1; j <= C; j++) input[i][j] = 'O';

			while (!q.empty()) {
				int x = q.front().first;
				int y = q.front().second;
				q.pop();

				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
					input[nx][ny] = '.';
				}
				input[x][y] = '.';
			}
			cnt += 2;
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++)
			cout << input[i][j];
		cout << "\n";
	}
}

 

---

시행착오

문제를 제대로 이해하지 못해서 오래 걸렸던 문제이고
BFS를 다양한 방식으로 구현하는 것이 중요하다는 것을 알려준 문제이다.

해당 문제의 풀이를 알아보면서
BFS를 확실히 이해한 것 같고 많이 공부됐다.