봄버맨

https://www.acmicpc.net/problem/16918

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	7889	3216	2314	41.218%

문제

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다.

즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다.

만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다.

따라서, 연쇄 반응은 없다.

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.

다음 1초 동안 봄버맨은 아무것도 하지 않는다.

다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다.

폭탄은 모두 동시에 설치했다고 가정한다.

1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.

3과 4를 반복한다.

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

예를 들어, 초기 상태가 아래와 같은 경우를 보자.

입력

첫째 줄에 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

예제 입력 2 

6 7 4
.......
...O...
....O..
.......
OO.....
OO.....

예제 출력 2

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

예제 입력 3

6 7 5
.......
...O...
....O..
.......
OO.....
OO.....

예제 출력 3

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

힌트

아래는 시간이 지난 후 예제 격자판의 상태이다.

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 시뮬레이션

---

폭발할 폭탄의 리스트를 작성하는 함수

맵의 빈 공간을 폭탄으로 바꾸어주는 함수

리스트의 폭탄을 폭발시키는 함수

폭탄은 한번에 폭발함으로 맵에 있는 폭탄과는 관계가 없이 리스트의 폭탄 위치의 상/하/좌/우 를 빈공간으로 만들어 줍니다.

빈공간으로 바꾸어줄떄 허용된 범위를 벗어나는지 체크

위의 기능들을 따로 구현하고 힌트에서 알려주는 로직대로 코드를 작성하였습니다.

통과된 코드

#include <iostream>
#include <list>

using namespace std;

// R, C, N 의 최대값 매크로
constexpr auto MAX = 200;

// 격자판 구현
// 범위 0 ~ 199
char map[MAX][MAX];

// 디버그용
bool debug = true;

int R, C, N;

// 지난 시간을 카운트
int timeCnt;

// 폭발할 폭탄의 위치를 가지는 리스트
list<pair<int, int>> locationBombList;
list<pair<int, int>>::iterator iterListBomb;

// 폭탄의 터지는 방향 정의
int dirExplosion[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };


// 시각적을 확인하기 위함
void DebugPrint()
{
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cout << map[i][j]; //<< " ";
		}

		cout << "\n";
	}
}

// 초기화를 하는 함수
void Initialization()
{
	// 시간 초기화
	timeCnt = 0;

	// 모두 빈칸으로 초기화
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			map[i][j] = '.';
		}
	}
}

// 입력을 받는 함수
void GetInput()
{
	cin >> R >> C >> N;

	// 초기 맵 입력받기
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> map[i][j];
		}
	}
}



// 폭발할 폭탄의 리스트를 작성합니다.
void CreateBombList()
{
	// 리스트를 초기화
	locationBombList.clear();

	// 정해진 범위 내에서 폭탄을 찾아서 리스트에 추가합니다.
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (map[i][j] == 'O')
			{
				locationBombList.push_back(make_pair(i, j));
			}
		}
	}
}

// 빈공간이면 폭탄으로 바꾸어 줍니다.
void BlankSpaceBombFilling()
{
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (map[i][j] == '.')
			{
				map[i][j] = 'O';
			}
		}
	}
}

// 리스트의 폭탄을 폭발시킵니다.
void bombExplosion()
{
	pair<int, int> tempPair;

	for (iterListBomb = locationBombList.begin(); iterListBomb != locationBombList.end(); iterListBomb++)
	{
		tempPair.first = iterListBomb->first;
		tempPair.second = iterListBomb->second;

		//자신의 위치를 빈공간으로 만들어 줍니다.
		map[tempPair.first][tempPair.second] = '.';

		// 폭탄의 상 하 좌 우를 빈공간으로 만들어 줍니다.
		for (int i = 0; i < 4; i++)
		{
			// 허용된 범위를 벗어나면 넘긴다.
			if (tempPair.first + dirExplosion[i][0] <= -1 || tempPair.first + dirExplosion[i][0] >= R 
				|| tempPair.second + dirExplosion[i][1] <= -1 || tempPair.second + dirExplosion[i][1] >= C)
			{
				continue;
			}

			// 상하좌우를 빈공간으로 만들어줍니다. (폭발 효과)
			switch (i)
			{
				case 0:
					map[tempPair.first + dirExplosion[i][0]][tempPair.second + dirExplosion[i][1]] = '.';
					break;

				case 1:

					map[tempPair.first + dirExplosion[i][0]][tempPair.second + dirExplosion[i][1]] = '.';
					break;

				case 2:
					map[tempPair.first + dirExplosion[i][0]][tempPair.second + dirExplosion[i][1]] = '.';
					break;

				case 3:
					map[tempPair.first + dirExplosion[i][0]][tempPair.second + dirExplosion[i][1]] = '.';
					break;
			}

		}
	}
}

// 게임을 시작
void StartGame()
{
	CreateBombList();
	timeCnt++;
	if (timeCnt == N) { return; }

	BlankSpaceBombFilling();
	timeCnt++;
	if (timeCnt == N) { return; }

	// 원하는 시간이 될때까지 진행
	while (true)
	{
		bombExplosion();
		CreateBombList();
		timeCnt++;
		if (timeCnt == N) { break; }

		BlankSpaceBombFilling();
		timeCnt++;
		if (timeCnt == N) { break; }
	}
}

int main()
{
	Initialization();
	GetInput();
	StartGame();

	if (debug) { DebugPrint(); }

	return 0;
}

틀린 이유는 백준에서 출력에 띄어쓰기가 있으면 안됨…..