[BOJ 16918] 봄버맨

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

16918번: 봄버맨

 

처음에는 다음 네 과정이 반복되는 줄 알았다.

초기 상태 > 폭탄이 가득 찬 상태 > 초기에 설치된 폭탄이 터진 상태 > 폭탄이 가득 찬 상태

그래서, n을 4로 나눈 나머지가 1일 때와 3일 때, 그리고 n이 짝수일 때 세 가지 경우가 생길 것을 판단해서 단순히 나머지로 케이스를 나누었으나 틀렸다.

 

위 사이클을 한 번 돈 다음에 초기 상태와 같지 않은 반례가 있었다.

3 4 5

OOO.

OOOO

OOOO 

위 예의 경우, 5초 후에는 전체가 빈 칸이 된다.

즉, n이 1일 때, 2로 나누어 떨어질 때, n이 4보다 크고 나머지가 1일 때, 나머지가 3일 때의 네 가지 상태가 존재하는 것이다.

 

그냥 각 상태를 재현해서 무식하게 풀었다.

#include <iostream>
#include <vector>
#include <utility>

void	printBoard(char board[200][200], int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			std::cout << board[i][j];
		}
		std::cout << '\n';
	}
}

void	getBombCoordinates(std::vector<std::pair<int, int> > &bomb,
							 char board[200][200], int r, int c)
{
	std::pair<int, int> temp;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (board[i][j] == 'O') {
				temp.first = i;
				temp.second = j;
				bomb.push_back(temp);
			}
		}
	}
}

void	explodeBomb(std::vector<std::pair<int, int> > &bomb,
						 char board[200][200], int r, int c)
{
	std::vector<std::pair<int, int> >::iterator it = bomb.begin();
	std::vector<std::pair<int, int> >::iterator end = bomb.end();

	while (it != end) {
		int i = (*it).first;
		int j = (*it).second;
		board[i][j] = '.';
		if (i > 0) {
			board[i - 1][j] = '.';
		}
		if (i < r - 1) {
			board[i + 1][j] = '.';
		}
		if (j > 0) {
			board[i][j - 1] = '.';
		}
		if (j < c - 1) {
			board[i][j + 1] = '.';
		}
		++it;
	}
}

void	setBomb(char board[200][200], int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			board[i][j] = 'O';
		}
	}
}

int main(void) {
	int r, c, n;		
	char board[200][200];

	std::cin >> r >> c >> n;
	std::cin.ignore();

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			std::cin >> board[i][j];
		}
		std::cin.ignore();
	}	

	if (n == 1) {
		printBoard(board, r, c);
		return 0;
	}

	if (n % 2 == 0) {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				std::cout << 'O';
			}
			std::cout << '\n';
		}
		return 0;
	}

	std::vector<std::pair<int, int> > bombA;
	std::vector<std::pair<int, int> > bombB;

	getBombCoordinates(bombA, board, r, c);

	for (int i = 2; i <= n; i++) {
		if (i % 2 == 0) {
			setBomb(board, r, c);
		} else if (i % 4 == 1) {
			explodeBomb(bombB, board, r, c);
			bombB.clear();
			getBombCoordinates(bombA, board, r, c);
		} else if (i % 4 == 3) {
			explodeBomb(bombA, board, r, c);
			bombA.clear();
			getBombCoordinates(bombB, board, r, c);
		}
	}

	printBoard(board, r, c);
	
	return 0;
}