[백준/구현/BFS&DFS/C++] 2573번 빙산

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

2573번: 빙산

문제 해결 방법

수도코드로 표현하면 아래처럼 표현할 수 있다.

while(1){
 if(빙하의 개수==0) break;
 빙하 덩어리 수 세기();
 
 if(빙하 덩어리수 > 1) break;
 else 빙하 녹이기();
}

그리고 크게 구현할 것은 아래  3가지 이다.

1. 빙하마다 바다에 둘러싸인 면의 수 구하기

2. 한번에 녹이기

3. 덩어리 수 세기

우선 입력받을 때 빙하는 queue에 넣어주었다.

그리고 덩어리 수를 셀때는 BFS를 사용했다.

void countIceLand(int a, int b){
    queue<pair<int, int>> q;
    q.push({a, b});
    isVisited[a][b] = true;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
            if(!isVisited[nx][ny] && MAP[nx][ny]>0){
                isVisited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

 

빙하가 녹는 부분은 이렇게 구현했다. 

1. queue에 넣은 빙하를 pop하고 바다와 닿은 면의 개수를 세서 다시 queue에 넣기

2. queue에 넣은 빙하를 pop하고 면의 개수만큼 빙하 높이에서 빼고 그 높이가 0보다 큰 경우 다시 queue에 넣기

동시에 하지않은 이유는 낮은 빙하가 바다가 되어버리면 결과가 달라지기 때문이다.

void meltGlac(){

    // 바다와 닿는 면의 수 구하기
    int size = glacier.size();
    for(int g=0; g<size; g++){
        int x = glacier.front().x;
        int y = glacier.front().y;
        glacier.pop();
        int cnt =0;

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
            if(MAP[nx][ny] == 0) cnt += 1;
        }
        glacier.push({x, y, cnt});
    }
    // 한번에 녹기
    for(int g=0; g<size; g++){
        int x = glacier.front().x;
        int y = glacier.front().y;
        int cnt = glacier.front().cnt;
        glacier.pop();

        MAP[x][y] -= cnt;
        if(MAP[x][y] < 0) MAP[x][y] = 0;
        if(MAP[x][y] > 0) glacier.push({x, y, MAP[x][y]});
    }
}

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

struct Point{
    int x;
    int y;
    int cnt; // 바다와 닿는 면의 수
};

int N, M;
int MAP[301][301];
queue<Point> glacier;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
int year = 0;
bool isVisited[301][301];
int countG;

void countIceLand(int a, int b){
    queue<pair<int, int>> q;
    q.push({a, b});
    isVisited[a][b] = true;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
            if(!isVisited[nx][ny] && MAP[nx][ny]>0){
                isVisited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

void meltGlac(){

    // 바다와 닿는 면의 수 구하기
    int size = glacier.size();
    for(int g=0; g<size; g++){
        int x = glacier.front().x;
        int y = glacier.front().y;
        glacier.pop();
        int cnt =0;

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
            if(MAP[nx][ny] == 0) cnt += 1;
        }
        glacier.push({x, y, cnt});
    }
    // 한번에 녹기
    for(int g=0; g<size; g++){
        int x = glacier.front().x;
        int y = glacier.front().y;
        int cnt = glacier.front().cnt;
        glacier.pop();

        MAP[x][y] -= cnt;
        if(MAP[x][y] < 0) MAP[x][y] = 0;
        if(MAP[x][y] > 0) glacier.push({x, y, MAP[x][y]});
    }
}

void clearVisit(){
    for(int i=1; i<N-1; i++){
        for(int j=1; j<M-1; j++){
            isVisited[i][j] = false;
        }
    }
}

void solve(){

    while(1){
        if(glacier.size()==0) break;
        clearVisit();
        // 덩어리 수 세기
        countG = 0;
        for(int i=1; i<N-1; i++){
            for(int j=1; j<M-1; j++){
                if(MAP[i][j]!=0 && !isVisited[i][j]){
                    countIceLand(i, j);
                    countG += 1;
                }
            }
        }

        if(countG>1) break;
        else meltGlac();
        year += 1;
    }
}

void input(){
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            int x;
            cin >> x;
            MAP[i][j] = x;
            if(x != 0) glacier.push({i, j, 0});
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solve();

    if(countG>1) cout << year;
    else cout << 0;

    return 0;
}