[백준/BOJ] 10711 모래성★ - 접근과 풀이 (c++)

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

10711번: 모래성

html 공부를 열심히 하다가 머리를 식히려고 들어간 백준이었으나 호되게 당해버린 문제.

알고리즘 공부는 무조건 꾸준히 하는걸로..

---

 접근방법

파도가 칠 때마다 모래성이 부서진다. 모래의 강도가 최대 9이므로, 모든 모래에 대해 완전탐색으로 풀려고 하였다. 더이상 모래가 부서지지 않을 때까지 O(1000*1000*@) 탐색을 돌렸는데, 당연히 시간초과를 받았다. 조금만 생각해서, 정답을 최대로 만드는 테스트케이스를 만든다면, 50만정도 나오겠어서 생각을 바꿨다.

 

모든 모래에 대해 탐색하지 않고, 부서지는 모래가 생기면 부서진 주변의 모래만 queue에 넣어서 접근했다. 이렇게 하면 최대 O(1000*1000*8) 정도 될 것 같아서 시도했다. 

 

코드를 작성하는 과정에서 현 단계에서 부서진 모래가 다른 모래에 영향을 미쳐서 고생 깨나 했다. 두 배열을 만들어서 toggle로 주고받기도 하고, 단계가 끝날때마다 복사하며 풀기도 했는데, 배열에서 모래를 저장할 때 모래가 깨진 시점의 깊이(파도 친 횟수)를 저장하여 해결했다. 

 

---

풀이 

#include<iostream>
#include<cstring>
#include<queue>
#include<utility>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int dy[8]={-1,-1,-1,0,1,1,1,0};
int dx[9]={-1,0,1,1,1,0,-1,-1};
int H,W;
int arr[1001][1001]={0}; //ans번째에 부서진 모래
queue<pii> q; //부서진곳 주변만 넣는 큐

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int ans=1,flag=0;
    char tmp;
    cin>>H>>W;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin>>tmp;
            if(tmp=='.') arr[i][j]=0;
            else arr[i][j]=-(tmp-'0');
        }
    }
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(arr[i][j]>=0 || arr[i][j]==-9) continue;
            int cnt=0;
            for(int k=0;k<8;k++){
                int ny=i+dy[k];
                int nx=j+dx[k];
                if(arr[ny][nx]>=0 && arr[ny][nx]!=ans) cnt++; //모래이면서 방금부서진게아님
            }
            if(cnt>= -arr[i][j]){ //부수자
                flag=1;
                arr[i][j]=ans;
                for(int k=0;k<8;k++){
                    int ny=i+dy[k];
                    int nx=j+dx[k];
                    if(arr[ny][nx]>=-8 && arr[ny][nx]<=-1){ //나보다 위,왼쪽인경우 존재하나?
                        q.push(mp(ny,nx));
                    }
                }
            }
        }
    }
    if(flag==0){
        cout<<"0";
        return 0;
    }

    flag=0;
    while(1){
        flag=0;
        ans++;
        int qs=q.size();
        for(int i=0;i<qs;i++){
            pii deq=q.front(); //한 depth에서 여러번 들어온 좌표가 부서지지 않는 경우 *8?
            int deqy=deq.first;
            int deqx=deq.second;
            q.pop();
          
            if(arr[deqy][deqx]>=0) continue; //q에 넣고보니 부서짐
           
            int cnt=0;
            for(int k=0;k<8;k++){
                int ny=deqy+dy[k];
                int nx=deqx+dx[k];
                if(arr[ny][nx]>=0 && arr[ny][nx]!=ans) cnt++;
            }
            
            if(cnt>= -arr[deqy][deqx]){ //부수자
                flag=1;
                arr[deqy][deqx]=ans;
                for(int k=0;k<8;k++){
                    int ny=deqy+dy[k];
                    int nx=deqx+dx[k];
                    if(arr[ny][nx]>=-8 && arr[ny][nx]<=-1) //나보다 위,왼쪽인경우 존재하나?
                        q.push(mp(ny,nx));
                }
            }
        }
        if(flag==0) break;
        
    }
    cout<<ans-1;
}

다 풀고 너무힘들어서 다른사람의 풀이를 살펴보니, 모래를 부수면 해당 모래의 위치를 queue에, 즉 파도치는 곳을 queue에 넣어서 푸니 되게 깔끔하고 간단해 보였다. 위의 풀이는 비추하며.. 나중에 새로 풀어봐야겠다.