[백준] 16918. 봄버맨

백준 문제 풀이

 

[백준] 16918. 봄버맨

16918번: 봄버맨

 

---

 

문제 해석 및 접근 방법

처음 폭탄을 설치하고, 2초에 빈 칸들에 새롭게 폭탄을 설치한다.
그 후 3초째에는 처음 설치한 폭탄이 폭발하고 4초째에 폭발한 자리가 비었으므로 다시 새로운 폭탄을 설치한다.

다음과 같은 패턴이 반복됨을 알 수 있다

폭탄은 3초 뒤에 폭발하고, 폭발 시에는 연쇄 반응 없이 상하좌우 4개를 같이 폭발시킨다.
따라서 처음 상태가 주어졌을 때, N초가 지난 후의 격자판 상태를 구하려 하는 문제이다.

 

처음 폭탄이 주어지면, 폭탄의 상하좌우만 변하고 나머지는 변화가 없음을 알 수 있다.
그림으로 이를 표현해 보았다.

처음 설치한 폭탄이 검은색 동그라미라고 하면, 1초 뒤에는 검은색 동그라미 부분에만 폭탄이 설치되어 있을 것이다. 2초가 되면 모든 칸에 폭탄이 채워지게 된다.
3초가 될 때에는 검은색 칸과 회색 칸이 모두 같이 터질 것이다.
4초가 될 때에는 다시 모든 칸에 폭탄이 채워진다.
5초가 되면, 흰색과 그 주변 회색 칸이 같이 터진다.
6초가 되면 다시 모든 칸에 폭탄이 채워진다.
7초가 되면 검은색 칸과 회색 칸이 같이 터진다.
...

따라서 1초일 때는 입력받은 그대로 출력하면 되고,
2초 이상일 때에는

• 짝수인 경우에는 모든 칸에 채워진 칸으로 출력
• 홀수일 경우에는 4로 나누어
  • 나머지가 3일 경우에는 (3,7,11 ... ) 처음 설치한 폭탄과 연관된 폭탄들이 터진 상태 출력 (위의 그림에서 흰색만 남은 상태 출력)
  • 나머지가 1일 경우에는 (5,9,13 ... ) 흰색 부분과 붙어 있는 부분이 터진 상태 출력

 

풀이

N에 따라 답이 갈라지는 것을 생각하여 작성하였다.

char board[201][201];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };

보드를 나타낼 배열과 상하좌우를 변수로 저장한다

 

void PrintSolution(int R, int C) {
	for (int x = 0; x < R; x++)
	{
		for (int y = 0; y < C; y++)
		{
			cout << board[x][y];
		}
		cout << "\n";
	}
}

출력도 함수로 빼 두었다.

 

문제의 케이스는 N에 따라 

1. N == 1일 경우
2. N이 짝수일 경우
3. N%4 == 3일 경우
4. N%4 == 1일 경우

로 나누었다.

 

1. N==1일 경우

	else if (N == 1) {
		// N이 1일 때에는 그대로 출력
		for (int x = 0; x < R; x++)
		{
			for (int y = 0; y < C; y++)
			{
				cin >> board[x][y];
			}
		}
	}

입력받은 그대로 출력했다.

 

2. N이 짝수일 경우

	if (N % 2 == 0) {
		// N이 짝수일 때에는 모든 칸에 폭탄이 있는 것으로 출력
		for (int x = 0; x < R; x++)
		{
			for (int y = 0; y < C; y++)
			{
				cin >> board[x][y];
				board[x][y] = 'O';
			}
		}
	}

입력을 받아 놓고 전부 O으로 바꾸었다

 

3. N%4 == 3일 경우

	else if (N % 4 == 3) {
		// 나머지가 3일 경우에는 반대로 넣어준 뒤, '.'주변의 한칸을 '.'로 바꿔준 뒤 리턴한다.
		vector<pair<int, int>> bombs;
		for (int x = 0; x < R; x++)
		{
			for (int y = 0; y < C; y++)
			{
				cin >> board[x][y];
				if (board[x][y] == '.') {
					board[x][y] = 'O';
				}
				else {
					board[x][y] = '.';
					bombs.push_back(make_pair(x, y));
				}
			}
		}

		for (int i = 0; i < bombs.size(); i++)
		{
			int cur_x = bombs[i].first;
			int cur_y = bombs[i].second;

			for (int j = 0; j < 4; j++)
			{
				int next_x = cur_x + dx[j];
				int next_y = cur_y + dy[j];

				if (next_x >= 0 && next_x < R && next_y >= 0 && next_y < C && board[next_x][next_y] == 'O') {
					board[next_x][next_y] = '.';
				}
			}
		}
	}

나머지가 3일 경우에는 처음 주어진 폭탄 주변의 폭탄들이 전부 터진다. 따라서 그냥 반대로 넣어 주고 주변을 .으로 바꾸도록 작성했다.

 

4. N%4 == 1일 경우

	else if (N % 4 == 1) {
		// 나머지가 1일 경우에는 그대로 넣어준 뒤, 'O'주변의 한칸을 'O'로 바꿔준 뒤 리턴한다.
		vector<pair<int, int>> bombs;
		for (int x = 0; x < R; x++)
		{
			for (int y = 0; y < C; y++)
			{
				cin >> board[x][y];
				if (board[x][y] == 'O') {
					bombs.push_back(make_pair(x, y));
				}
			}
		}

		while (!bombs.empty())
		{
			int cur_x = bombs.back().first;
			int cur_y = bombs.back().second;
			bombs.pop_back();

			for (int j = 0; j < 4; j++)
			{
				int next_x = cur_x + dx[j];
				int next_y = cur_y + dy[j];

				if (next_x >= 0 && next_x < R && next_y >= 0 && next_y < C && board[next_x][next_y] == '.') {
					board[next_x][next_y] = 'O';
				}
			}
		}

		for (int x = 0; x < R; x++)
		{
			for (int y = 0; y < C; y++)
			{
				if (board[x][y] == '.') {
					bombs.push_back(make_pair(x, y));
				}
			}
		}

		while (!bombs.empty())
		{
			int cur_x = bombs.back().first;
			int cur_y = bombs.back().second;
			bombs.pop_back();

			for (int j = 0; j < 4; j++)
			{
				int next_x = cur_x + dx[j];
				int next_y = cur_y + dy[j];

				if (next_x >= 0 && next_x < R && next_y >= 0 && next_y < C && board[next_x][next_y] == 'O') {
					board[next_x][next_y] = '.';
				}
			}
		}
	}

이 부분에서 헷갈려서 몇 번 틀렸다ㅜㅜ

정확히는 위의 그림에서 흰색 부분과 붙어있는 회색 부분이 터진 상태를 출력하면 된다.
이를 출력하기 위해 먼저 처음 주어진 폭탄 주변을 O으로 바꾼 뒤, 한번 더 보드를 읽어서 .인 부분을 찾는다(그림에서 흰색 부분)
그 후 다시 찾아낸 주변 부분을 터트리면 된다.

 

전체 소스코드 (Github)