풀이 보관함
[C++] 백준 16918번: 봄버맨 본문
🔗 문제
🖍 풀이
- 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
- 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
- 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
- 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
- 3과 4를 반복한다.
폭탄 터지는 조건
- 설치 후 3초 후 터진다.
- 터질 때 상하좌우자리도 빈칸이 된다.
- 상하좌우에 폭탄이 있어도 연쇄작용은 없다.
중요한 점은 폭탄을 동시에 터트려야 하는 것이다.
하나씩 폭탄을 터트리다보면 사방에 터져야할 폭탄도 제거하게 되어서 예제3에서 오답이 나온다.
이 부분을 해결하기 위해서 터트릴 폭탄을 따로 저장(tmp)해주고 제거해주었다.
💾 소스
#include <iostream>
#include <list>
const int MAX = 200 + 5;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
int R, C, N;
int timer[MAX][MAX] = {0, };
bool bomb[MAX][MAX] = {false, };
bool isValid(const int x, const int y)
{
if(x<0 || y<0 || x>=R || y>=C)
return false;
return true;
}
void display_timer()
{
for(int i=0; i<R; ++i)
{
for(int j=0; j<C; ++j)
{
std::cout << timer[i][j] << ' ';
}
std::cout << '\\n';
}
}
void display_map()
{
for(int i=0; i<R; ++i)
{
for(int j=0; j<C; ++j)
{
std::cout << (bomb[i][j] ? 'O' : '.' );
}
std::cout << '\\n';
}
}
void solve()
{
while(--N)
{
std::list<std::pair<int, int>> tmp;
for(int i=0; i<R; ++i)
{
for(int j=0; j<C; ++j)
{
if(bomb[i][j])
{
--timer[i][j];
}
else
{
// 빈 곳에 폭탄 설치
bomb[i][j] = true;
timer[i][j] = 3;
}
}
}
for(int i=0; i<R; ++i)
{
for(int j=0; j<C; ++j)
{
if(bomb[i][j] && timer[i][j] == 0)
{
tmp.push_back({i, j});
}
}
}
// 타이머대로 폭탄을 터트린다.
for(const auto& [i, j] : tmp)
{
bomb[i][j] = false;
timer[i][j] = 0;
for(int d=0; d<4; ++d)
{
int x = dx[d] + i;
int y = dy[d] + j;
if(!isValid(x, y)) continue;
bomb[x][y] = false;
timer[x][y] = 0;
}
}
}
}
int main()
{
std::cin >> R >> C >> N;
char tmp;
for(int r=0; r<R; ++r)
{
for(int c=0; c<C; ++c)
{
std::cin >> tmp;
if(tmp == 'O')
{
timer[r][c] = 2; // 처음에는 1초에는 아무것도 안하니까.
bomb[r][c] = true;
}
}
}
solve();
display_map();
return 0;
}