[백준 2573] 빙산 C++

2573번: 빙산

BFS

---

 

현재 맵의 빙산의 개수가 0이 될 때까지 반복문을 수행한다.

 

물과 접촉한 빙산의 높이를 줄여주는 BFS를 수행한다.

높이가 달라진 빙산들은 임시 맵과 큐에 따로 저장한다.

 

임시 맵의 정보를 기존 맵으로 복사한다.

 

임시 큐의 빙산 정보를 기존 큐의 빙산정보로 옮김과 동시에

높이가 달라진 빙산들이 서로 떨어졌는지 확인하는 BFS를 수행한다.

중간에 서로 떨어진 경우에는 현재 year를 출력하고 return 한다.

 

---

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
int Map[301][301];
int Tmap[301][301];
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
queue<pii > iceque, icetemp;
int year = 0;
 
bool visited[301][301];
 
void input(){
    cin >> N >> M;
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            cin >> Map[r][c];
            Tmap[r][c] = Map[r][c];
            if(Map[r][c]) iceque.push({r, c});
        }
    }
}
 
void BFS(){
    while(!iceque.empty()){
        pii now = iceque.front();
        iceque.pop();
        
        for(int k = 0; k < 4; k++){
            int nr = now.first + dr[k];
            int nc = now.second + dc[k];
            
            if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            
            if(!Map[nr][nc]){
                Tmap[now.first][now.second]--;
            }
        }
        if(Tmap[now.first][now.second] > 0){
            icetemp.push({now});
        }
        else Tmap[now.first][now.second] = 0;
    }
}
 
void show(){
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            Map[r][c] = Tmap[r][c];
        }
    }
}
 
void check(int r, int c){
    queue<pii > que;
    que.push({r, c});
    
    while(!que.empty()){
        pii now = que.front();
        que.pop();
        
        for(int k = 0; k < 4; k++){
            int nr = now.first + dr[k];
            int nc = now.second + dc[k];
            
            if(nr < 0 || nr >= N || nc < 0 || nc >= M || !Map[nr][nc] || visited[nr][nc]) continue;
            visited[nr][nc] = true;
            que.push({nr, nc});
        }
    }
}
 
void solve(){
    while(!iceque.empty()){
        year++;
        BFS();
        show();
        memset(visited, 0, sizeof(visited));
        
        int ct = 0;
        while(!icetemp.empty()){
            int r = icetemp.front().first;
            int c = icetemp.front().second;
            iceque.push(icetemp.front());
            if(!visited[r][c]){
                check(r, c);
                ct++;
            }
            if(ct > 1){
                cout << year;
                return;
            }
            icetemp.pop();
        }
    }
    cout << 0;
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}