[DFS] 백준 2573번 - 빙산

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

2573번: 빙산

정답률이 26%인 것에 비해서는 기다지 난이도가 있는 문제는 아니다.

이 문제는 시뮬레이션 + DFS 문제로 시간의 흐름에 따라 빙산을 녹여주는 시뮬레이션 코드와

녹은 빙산의 면적이 몇 개의 구역으로 나뉘는 지 DFS로 확인하는 문제다. 물론 BFS로 해도 상관은 없다.

 

아래는 코드 전체

#include <iostream>
#include <vector>
 
using namespace std;
 
int Time = 0;
bool found_answer = false;
int num_glacier = 0;
int N, M;
vector<vector<int> > map, Minus;
vector<vector<bool> > check;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void reset(){
    for (int r = 0; r < N; r++){
        for (int c = 0; c < M; c++){
            Minus[r][c] = 0;
            check[r][c] = false;
        }
    }
    num_glacier = 0;
}
 
bool checkAllClear(){
    bool AllClear = true;
    for (int r = 0; r < N; r++){
        for (int c = 0; c < M; c++){
            if (map[r][c]) {
                AllClear = false;
                break;
            }
        }
        if (!AllClear) break;
    }
    return AllClear;
}
 
void dfs(int r, int c){
    check[r][c] = true;
    for (int i = 0; i < 4; i++){
        int nr = r + direction[i].dr;
        int nc = c + direction[i].dc;
        if (nr >= 0 && nr < N && nc >= 0 && nc < M){
            if (!check[nr][nc] && map[nr][nc]){
                dfs(nr, nc);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    map.assign(N, vector<int>(M, 0));
    Minus.assign(N, vector<int>(M, 0));
    check.assign(N, vector<bool>(M, false));
    for (int r = 0; r < N; r++){
        for (int c = 0; c < M; c++){
            cin >> map[r][c];
        }
    }
    while (!checkAllClear()){
        Time++;
        // 1. 녹는다.
        for (int r = 0; r < N; r++){
            for (int c = 0; c < M; c++){
                if (map[r][c]){
                    int num_sea = 0;
                    for (int i = 0; i < 4; i++){
                        int nr = r + direction[i].dr;
                        int nc = c + direction[i].dc;
                        if (nr >= 0 && nr < N && nc >= 0 && nc < M){
                            if (map[nr][nc] == 0){
                                num_sea++;
                            }
                        }
                    }
                    Minus[r][c] = num_sea;
                }
            }
        }
        for (int r = 0; r < N; r++){
            for (int c = 0; c < M; c++){
                if (map[r][c]){
                    map[r][c] -= Minus[r][c];
                    if (map[r][c] < 0) map[r][c] = 0;
                }
            }
        }
        // 2. 갯수 센다.
        for (int r = 0; r < N; r++){
            for (int c = 0; c < M; c++){
                if (map[r][c] && !check[r][c]){
                    dfs(r, c);
                    num_glacier++;
                }
            }
        }
        if (num_glacier >= 2) {
            found_answer = true;
            break;
        }
        reset();
    }
    if (!found_answer){
        cout << "0\n";
        return 0;
    }
    cout << Time << '\n';
    return 0;
}