[BOJ] 백준 2573 빙산 c++ (bfs, 구현)

문제 출처 : https://www.acmicpc.net/problem/2573

2573번: 빙산

풀이

일년마다 주위(상하좌우)에 물이 있는 개수만큼 빙산이 녹는 방식인데, 빙산이 두개이상으로 분리되는 시간을 구하는 문제이다!

(빙산이 다 녹을 때까지 분리되지 않으면 0 출력)

 

먼저 2차원 배열을 입력받고

1. 4방향 탐색 후 물이 있는개수만큼 빼주기

2. 빙산이 분리되었는지 확인

3. 빙산이 다 녹았는지 확인

을 반복한다.

---

1. 4방향 탐색 후 물이 있는개수만큼 빼주기

처음 입력을 받을때 물이 아닌 입력(0이 아닌 입력)의 경우 따로 vector에 좌표를 저장해 놨었다.

해당 vector를 for루프를 돌며 0인 개수를 저장해 빼주면 된다.

이때 check 배열로 체크를 진행해야 중복을 방지할 수 있다!

2. 빙산이 분리되었는지 확인

bfs로 하나의 이어져있는 빙산의 개수를 샌다.

하나의 이어져있는 빙산의 개수가 남아있는 빙산의 수와 같다면 빙산이 분리되지 않은 것이다.

그 외에는 빙산이 분리되었으므로 결과를 출력한다.

3. 빙산이 다 녹았는지 확인

1번의 vector를 순환하며 0이 아닌 요소가 있다면 녹지 않은 것 이므로 false를 리턴하고, 모두 0이면 true를 리턴한다.

---

코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
int arr[300][300];
bool check[300][300];
int cnt;
int meltCnt = 0;
vector<pair<int, int>> input;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool check_end(){
    for(int i = 0; i < input.size(); i++){
        int row = input[i].first;
        int col = input[i].second;
        if(arr[row][col]) return false;
    }
    return true;
}

bool check_divide(){
    int inputCnt = 0;
    queue<pair<int, int>> q;
    for(int i = 0; i < input.size(); i++){
        int row = input[i].first;
        int col = input[i].second;
        if(!arr[row][col]) continue;
        else{
            q.push({row, col});
            break;
        }
    }
    while(!q.empty()){
        int row = q.front().first;
        int col = q.front().second;
        inputCnt++;
        q.pop();
        check[row][col] = true;
        for(int j = 0; j < 4; j++){
            int nRow = row + dy[j];
            int nCol = col + dx[j];
            if(check[nRow][nCol] || nRow < 0 || nRow >= N || nCol < 0 || nCol >= M)
                continue;
            if(arr[nRow][nCol]){
                check[nRow][nCol] = true;
                q.push({nRow, nCol});
            }
        }
    }
    memset(check, 0, sizeof(check));
    if(inputCnt == input.size() - meltCnt) return false;
    return true;
}

void do_solution(){
    for(int i = 0; i < input.size(); i++){
        int row = input[i].first;
        int col = input[i].second;

        if(!arr[row][col]) continue;

        check[row][col] = true;
        int oceanCnt = 0;
        for(int j = 0; j < 4; j++){
            int nRow = row + dy[j];
            int nCol = col + dx[j];

            if(check[nRow][nCol] || nRow < 0 || nRow >= N || nCol < 0 || nCol >= M)
                continue;
            if(!arr[nRow][nCol])
                oceanCnt++;
        }
        if(arr[row][col] - oceanCnt <= 0){
            meltCnt++;
            arr[row][col] = 0;
        }
        else arr[row][col] -= oceanCnt;
    }
    memset(check, 0, sizeof(check));
}

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

    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> arr[i][j];
            if(arr[i][j]) input.push_back({i, j});
        }
    }
    
    while(1){
        do_solution();
        cnt++; 
        if(check_divide()){
            cout << cnt << '\n';
            return 0;
        }
        if(check_end()){
            cout << 0 << '\n';
            return 0;
        }
    }
    return 0;
}