[C++] 백준 16918번: 봄버맨

🔗 문제

16918번: 봄버맨

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;
}