[BOJ] 16918 봄버맨

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

16918번: 봄버맨

 

그래프 이론과 구현이 융합된 문제이다.

처음에 아무것도 일어나지 않아 조금 헷갈리는 문제이나 실버여서 그런지 쉽다.

터져야 되는 폭탄을 queue에 넣고 3초 뒤에 그 size만큼 반복문을 돌리며 폭탄이 설치된 칸과 인접한 네칸을 빈 칸처리 해주었다.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int R,C,N;
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};

char map[200][200];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>R>>C>>N;
    queue<pair<int,int> > q;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            cin>>map[i][j];
            if(map[i][j]=='O') q.push(make_pair(i,j));
        }
    }
    
    N--;
    
    
    while(N){
        int s=q.size();
        //1초 후에 맵 전체에 폭탄
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j]=='.'){
                    map[i][j]='O';
                }
            }
        }

        if(--N==0) break;
        
        //1초 후에 전에 설치된 폭탄 폭파
        for(int i=0;i<s;i++){
            int y=q.front().first, x=q.front().second;
            q.pop();
            map[y][x]='.';
            for(int j=0;j<4;j++){
                int ny=y+dy[j], nx=x+dx[j];
                if(0<=ny&&ny<R&&0<=nx&&nx<C){
                    map[ny][nx]='.';
                }
            }
        }

        if(--N==0) break;
        
        //2초 뒤에 터질 폭탄 queue에 넣기
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j]=='O'){
                    q.push(make_pair(i,j));
                }
            }
        }
    }
    
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++) cout<<map[i][j];
        cout<<'\n';
    }
    return 0;
}