백준 16918번 봄버맨(c++)

문제 분석

봄버맨 문제를 읽고, 마땅한 알고리즘이 떠오르지 않았다. 어떤 알고리즘을 활용하기보다는 문제 자체에서 해결하는 구현에 초점을 맞춘 문제로 판단했다. 이는 3가지의 키워드를 잡고 접근하면 쉽게 해결할 수 있다.

1. 초기 설정 이후, 봄버맨은 1초간 아무것도 하지 않는다.
2. 다음 1초간 폭탄이 없는 곳에 폭탄을 설치한다.
3. 폭탄이 터지는 시간은 3초이며, 폭발위치에 폭탄은 연쇄반응을 하지 않는다.

특히 2, 3번의 동작을 반복하기에 2가지 중 가장 중요한 분석이 있다고 생각할 수 있으나,
필자는 1번이 가장 중요하다고 생각한다.

-> 1번을 살펴보면 초기 설정 이후 봄버맨은 계속해서 폭탄을 설치하고, 폭발하고를 반복하게 된다. 이 부분이 문제 전체에서 어색하다고 생각했고, 일정 규칙을 만들기 위한 조건이라고 생각했다!

---

문제 풀이

1번을 통해 문제의 규칙을 파악해보면...

 

1) 초기 설정과 1초일 경우, 어떤 변화도 있지 않다. (기존 폭탄 : 1, 새폭탄 : x)

 

2) 2초일 경우, 폭탄이 가득찬 땅이 형성된다. (폭탄의 시간은 제각각 다르다!)  (기존 폭탄 : 2, 새폭탄 : 0)

 

3) 3초일 경우, 초기 설치했던 폭탄이 폭발하고 주변 폭탄 또한 사라지게 된다.  (기존 폭탄 : 3 -> 0, 새폭탄 : 1)

    여기서 기존 폭탄이 없어지므로, 새폭탄이 기존 폭탄이 된다!

 

4) 4초일 경우, 폭발했던 위치에 다시 폭탄이 설치되고, 폭탄이 가득찬 땅이 형성된다. (기존 폭탄 : 2, 새폭탄 : 0)

 

5) 5초일 경우, 2초 떄 설치했던 폭탄이 폭발하고 주변 폭탄 또한 사라지게 된다. (기존 폭탄 : 3 -> 0 , 새폭탄 : 1)

 

6) 6초일 경우, 폭발했던 위치에 다시 폭탄이 설치되고, 폭탄이 가득찬 땅이 형성된다. (기존 폭탄 :2 , 새폭탄 : 0)

 

...

 

규칙이 있지 않나요?

• 시간이 짝수일 경우, 폭탄이 가득 찬 땅이 형성되고
• 시간이 홀수인 경우, 3초가 된 폭탄이 폭발하게 된다

이제 구현만 진행하면 된다! 일단 문제의 조건에 대한 2차원 배열을 2개 만든다. 

1번째는 폭탄의 시간을 측정하는 timer 역할

2번째는 실질적인 폭탄과 맨땅의 위치를 확인하는 역할

특히, 구현에서 배열의 범위에서 벗어나지 않도록 확인해 주는 것 또한 중요하다!

 

...

 

이대로면 완벽한 줄 알았으나 문제가 2가지 발생한다.

 

1. 

위 조건대로 폭탄이 폭발한다면, 2중 반복문의 특성상 동시적으로 배열의 모든 원소를 확인할 수 없다.

이는 터져야 하는 폭탄이 붙어있다면, 먼저 검사한 폭탄이 터져야 할 붙어있는 폭탄을 제거하게 된다.

그러면... 터져야하는 폭탄은 터지지 못한 채 없어지게 된다..

그러므로, 3초가 된 폭탄은 제거하지 못하게까지! 해야 한다.

 

2.

위처럼 순차 탐색을 하는 2중 반복문 특성상, 해당 폭탄이 시간이 지남과 동시에 주변 폭탄을 확인하게 할 경우 (2가지 동작을 하나의 2중 반복문안에 넣으면)

터져야 하는 폭탄이 붙어있다면, 옆에 있는 폭탄이 해당 시간에 터져야 하지만 순차 탐색에 의해 터져야 할 폭탄으로 인식하지 못할 수 있다. 그러므로 2중 반복문을 2개 사용하여 터져야 할 폭탄인지 아닌지 구분할 수 있도록 한다.

아래 코드를 보면서 다시 확인하길 바란다.

---

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int R, C, N;
	cin >> R >> C >> N;
	vector<vector<int>> stk(R, vector<int>(C, 0));
	vector<vector<char>> area(R, vector<char>(C, '.'));

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> area[i][j];
			if (area[i][j] == 'O')
				stk[i][j]++;
		}
	}
    // 입력받으면서, 초기 폭탄이 설치된 지역은 시간++함.
    // 초기 설정 후 1초까지 지난 상황을 기준으로 하기에

	int time = 1; // 초기 설정과 1초까지 변화가 없기에 1초부터 실행함.

	while (time < N) {
		time++;
		if (time % 2 == 0) { // 시간이 짝수일 경우
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if (area[i][j] == '.') { // 맨땅이면 폭탄 설치함.
						area[i][j] = 'O';
						stk[i][j] = 0;
					}
					else { // 폭탄이 있다면 폭탄 시간 추가
						stk[i][j]++;
					}
				}
			}
		}

		else { // 시간이 홀수일 경우
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					stk[i][j]++;
				}
			}
            // 먼저 모든 배열에 시간을 추가함.
            
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if (stk[i][j] == 3) { // 터져야 할 폭탄이 있다면
						stk[i][j] = 0;
						area[i][j] = '.';
						if (i + 1 < R && stk[i + 1][j] != 3) {
							area[i + 1][j] = '.';
							stk[i + 1][j] = 0;
						}
						if (j + 1 < C && stk[i][j + 1] != 3) {
							area[i][j + 1] = '.';
							stk[i][j + 1] = 0;
						}
						if (i - 1 >= 0 && stk[i - 1][j] != 3) {
							area[i - 1][j] = '.';
							stk[i - 1][j] = 0;
						}
						if (j - 1 >= 0 && stk[i][j - 1] != 3) {
							area[i][j - 1] = '.';
							stk[i][j - 1] = 0;
						}
					} // 폭탄이 폭발하면서 배열 범위와 터져아할 폭탄인지 확인함.

				}
			}

		}

	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cout << area[i][j];
		}
		cout << '\n';
	}


	return 0;
}

코드 리뷰는 언제나 환영입니다!