[SWEA] 1907 모래성 쌓기

 

BFS를 돌려서 푸는 문제다

성을 넣지말고 반대로 모래를 넣으면 쉽게 풀 수 있다

 

모래를 기준으로 8방향을 보면서 성이 있다면 1씩 감소시켜준다

만약 성의 견고함이 0이 된다면 모래로 바꾸고 큐에 넣어주면 된다

 

풀긴 풀었는데 시간이 좀 너무 오래걸렸다.. 왜지..!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int arr[1010][1010];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
int n,m;
 
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<m);
}
int main(){
    int t; scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        scanf(" %d %d",&n,&m);
 
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                char c; scanf(" %1c",&c);
                if('1'<=c&&c<='9') arr[i][j]=c-'0';
            }
        }
        
        queue<pair<int,int>> q;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]) continue;
                q.push({i,j});
            }
        }
        
        int ans=0;
        while(int s = q.size()){
            while(s--){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
 
                for(int i=0;i<8;i++){
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if(inner(nx,ny) && arr[nx][ny]){
                        arr[nx][ny]--;
                        if(!arr[nx][ny]) q.push({nx,ny});
                    }
                }
            }
            ans++;
        }
        printf("#%d %d\n",tc,ans-1);
    }
}