[백준][C++] 10711 모래성

www.acmicpc.net/problem/10711

10711번: 모래성

 

 

 

알고리즘 종류

    - 구현

    - BFS

 

 

 

사고 과정

    - 예시로 과정을 그려보면 아래와 같다.

    - 과정을 보면 다음과 같다.

        1. 모래성은 기존 주변 파도 개수와 비교

        2. 모래성은 기존 주변 파도 개수 + 새로 생성된 파도 개수와 비교

        3. 모래성은 기존 주변 파도 개수 + 새로 생성된 파도 개수 + 새로 생성된 파도 개수와 비교

        4. 모래성은 기존 주변 파도 개수 + 새로 생성된 파도 개수 + 새로 생성된 파도 개수 + 새로 생성된 파도 개수와 비교

 

    - 규칙이 보이는 것 같다. 이전에 생성된 파도를 계속 빼주고 있다. 중복해서 매번 빼준다는 의미이다. 그렇다면 애초에 미리 빼버리면 어떨까?

 

        1. 주변 파도 개수를 빼면 아래와 같이 강도가 줄어들고, 초록색의 새로운 파도 구역이 생긴다.

        2. 주변 파도 개수를 빼면 아래와 같이 강도가 줄어들고, 노란색의 새로운 파도 구역이 생긴다.

        3. 주변 파도 개수를 빼면 아래와 같이 강도가 줄어들고, 붉은색의 새로운 파도 구역이 생긴다.

        4. 주변 파도 개수를 빼면 아래와 같이 강도가 줄어들고, 더 이상 파도 구역이 생기지 않고 종료된다.

 

 

구현(C++)

#include <iostream>
#include <queue>
 
using namespace std;
 
int h, w;
 
int mat[1001][1001];
int dir[8][2] = {{1,0}, {1,1}, {0,1}, {-1,1}, {-1,0}, {-1,-1}, {0,-1}, {1,-1}};
 
queue<pair<int, int> > q;
 
 
bool isValid(int y, int x){
    return (x>=0 && x<w) && (y>=0 && y<h);
}
 
 
void solution(){
    
    int answer = 0;
    while(!q.empty()){
        
        int size = q.size();
        for(int i=0; i<size; i++){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
 
            for(int d=0; d<8; d++){
                int ny = y + dir[d][0];
                int nx = x + dir[d][1];
                
                if(!isValid(ny, nx)) continue;
                if(mat[ny][nx] == 0) continue;
                
                mat[ny][nx]--;
                if(mat[ny][nx] == 0) 
                    q.push({ny, nx});
            }
        }
        
        answer++;
    }
    
    cout << answer-1;
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> h >> w;
    
    char c;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> c;
            if(c == '.'){
                q.push({i, j});
                mat[i][j] = 0;
            } 
            else mat[i][j] = c - '0';
        }
    }
    
    solution();
    
}
 

 

 

 

시행착오

    - 총 4번의 다른 풀이를 해봤다.

        1. 2중 for문으로 전체 순환 => 시간 초과

        2. queue에 모래성만 넣고 주변을 탐색해서 파도 개수와 비교하는 BFS => 시간 초과

        3. queue에 모래성만 넣고 모래가 사라지면 주변 모래성에 파도 개수 변수 증가시키는 BFS => 시간 초과

        4. 도저히 시간을 줄일 수 있는 방법이 떠오르지 않아서, 이 분의 블로그를 참고했다.

 

    - 위와 같은 풀이를 떠올리기 위해서는 어떻게 접근해야 했을까? 전체 과정을 그려볼 수 있다면, 그려보고 규칙을 찾아보면 좋을 것 같다. 

        * 아래와 같이 시간에 따라 과정을 표현하지 않은 풀이가 아닌,

        * 아래와 같이 시간에 따라 과정을 볼 수 있는 표현을 사용해 보자. 그러면 과정에서 규칙을 찾을 수 있을 것이다.