[백준] 모래성

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

10711번: 모래성

BFS를 이용하는 문제입니다.

 

문제부터 간단하게 요약해보면, 

모래성이 있고, 파도가 치는 상황이 주어집니다. 매 파도가 칠 때, 파도와 가로 세로 대각선으로 닿는 부분이 강도보다 크거나 같은 경우 무너지게 됩니다. 

 

이 때, 총 몇번의 파도가 몰려오고 나서 모래성이 수렴하는지를 구해야 하는 문제입니다.

 

<Solution>

queue에 파도를 넣어 bfs를 이용하면 됩니다. 이 때, 몇번 파도인지 에 따라 값을 올려주어야 하므로, for loop를 이용해 현재 queue의 사이즈 만큼만 빼는 형태로 구현하였습니다. 이렇게 구현하면, 파도가 칠 때 마다 해당 파도에 해당하는 만큼만 pop될 것이기 때문입니다. 

 

종료 조건은 더이상 파도에 의해 부서지지 않아서 queue가 빌 때로 설정하면 됩니다.

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
#define MAXN (1000)
int H, W;
char map[MAXN+10][MAXN+10];
 
struct rc{
    int r, c;
};
 
int d_row[] = {0, 0, -1, 1, 1, 1, -1, -1};
int d_col[] = {1, -1, 0, 0, 1, -1, 1, -1};
 
void InputData(){
    cin >> H >> W; // R C
    for (int i=0; i<H; i++){
        cin >> map[i];
    }
}
 
 
int solution(){
 
    queue <rc> q;
    for(int i = 0; i<H; i++){
        for(int j = 0; j<W; j++){
            if(map[i][j] == '.'){
                q.push((rc){i,j});
            }
        }
    }
    int cnt = -1;
    while(!q.empty()){

        int tmp = q.size();
        for(int i = 0; i<tmp; i++){
            rc cur = q.front(); q.pop();
 
            int next_r,next_c;
 
            for(int j = 0; j<8; j++){
                next_r = cur.r + d_row[j];
                next_c = cur.c + d_col[j];
 
                // out of bound
                if(!(0<= next_r && next_r <H && 0<=next_c && next_c < W)) continue;
 
                if('0'<map[next_r][next_c] && map[next_r][next_c] <= '9'){
                    map[next_r][next_c] --;
                    if(map[next_r][next_c] == '0'){
                        map[next_r][next_c] = '.';
                        q.push(rc{next_r,next_c});
                    } 
                }
            }
        }
        cnt ++;
 
    }
 
    return cnt;
 
 
}
 
int main(){
    int ans = -1;
 
    InputData();

    ans = solution();
 
    cout << ans << endl;
    return 0;
}