[BOJ] 2573번 : 빙산(C++)

문제 링크 : 백준 2573번

[문제 접근]

문제에서 요구한데로 구현하면 되는 문제이다.

1. 처음은 무조건 빙산이 녹아야하므로 do-while문을 이용한다.
2. melt함수로 들어가 빙산이 녹는 단계를 진행한다.
   • arr배열을 변경하지않고 temp배열에 arr배열에서 빙산이 녹은 경우를 저장한다.
     - arr배열을 변경하게되면 변경 도중에 빙산이 0인 경우가 생겨서 잘못하면 주변 빙산이 더 녹을 수도 있다.
   • 빙산이 녹은 경우를 진행했으면 arr배열에 temp배열을 복사해서 빙산이 녹은 경우를 arr배열에 갱신해준다.
3. 빙산이 두 덩어리 이상으로 나뉘는 지 check함수를 통해 검사한다.
   • 한 덩어리면 2번으로 돌아가서 계속 do-while문을 돈다.
   • 두 덩어리 이상이면 do-while문을 탈출한다.
   • 한 덩어리도 남아있지 않다면 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지않는다는 말이므로 0을 출력해준다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

int n, m;
int arr[301][301];
int temp[301][301];
bool visit[301][301];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
bool reans = true;

void BFS(int s, int e) {
    queue<pair<int, int> > q;
    q.push(make_pair(s, e));
    visit[s][e] = 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 || nx>=n || ny<0 || ny>=m) continue;
            if(arr[nx][ny] != 0 && !visit[nx][ny]) {
                q.push(make_pair(nx, ny));
                visit[nx][ny] = true;
            }
        }
    }
}

bool check() {
    memset(visit, false, sizeof(visit));
    int cnt=0;
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) {
            if(arr[i][j] != 0 && !visit[i][j]) {
                BFS(i, j);
                cnt++;
            }
        }
    }
    if(cnt==0) {
        reans = false;
        return false;
    } else if(cnt == 1) {
        return true;
    } else {
        return false;
    }
}

void melt() {
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) {
            if(arr[i][j] != 0) {
                int x = i , y = j, cnt=0;
                for(int k=0 ; k<4 ; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];

                    if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
                    if(arr[nx][ny] == 0) cnt++;
                }
                if(arr[x][y]-cnt<0) {
                    temp[x][y] = 0;
                } else {
                    temp[x][y] = arr[x][y]-cnt;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) {
            cin >> arr[i][j];
        }
    }

    int ans=0;
    do{
        memset(temp, 0, sizeof(temp));
        melt();
        ans++;
        memcpy(arr, temp, sizeof(arr));
    }while(check());

    if(reans) {
        cout << ans;
    } else {
        cout << 0;
    }
    return 0;
}