백준 2573 - 빙산 - DFS

문제

문제링크 : https://www.acmicpc.net/problem/2573

풀이전략

1. 가로세로에 닿아있는 바다의 개수만큼 값이 줄어든다. 따라서 각 빙산마다 가로세로의 닿아있는 바다의 개수를 구해야한다.
2. 이 문제에 경우 빙산을 순차적으로 없애주는 것이 아니라, 각 빙산마다 가로세로 닿아있는 바다의 개수를 배열에 저장하고, 모든 개수를 구하면 이후에 빙산에서 빼주어야한다. 순차적으로 없애줄경우 중간에 바다가 하나 더 생겨 오류가 발생한다.
3. 두 덩어리 이상으로 분리됨을 찾아야 하므로, 이후 빙산의 영역찾기를 DFS로 하면된다.

코드

#include<bits/stdc++.h>

using namespace std;

int R, C;
// 빙산
int a[302][302];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
// 몇 해가 지났는지를 구해주는 변수
int year = 0;
// 빙산의 덩어리의 개수
int landCnt = 0;
// 이동에 관해 필요한 체크배열
bool ch[302][302];
// 빙산이 다 녹아도 분리되지 않았을 경우를 찾는것.... 지금보니 없어도 풀게 만들수 있음
bool flag = false;
// 나중에 일괄적으로 빙산의 녹은 값을 빼줌을 위한 배열
int afterYearMinus[302][302];
void afterOneYear(){
    memset(afterYearMinus, 0, sizeof(afterYearMinus));
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            if(a[i][j] > 0){
                
                for(int k=0; k<4; k++){
                    int ii = i+dy[k];
                    int jj = j+dx[k];
                    // 주변에 바다가 있을경우 빼줄 값을 더해준다.
                    if(a[ii][jj] == 0) afterYearMinus[i][j]++;
                }
            }
        }
    }
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            a[i][j] = a[i][j] - afterYearMinus[i][j];
            // 빙산이 녹으면 바다가 되므로 0보다 작을경우 바다로 인식하지 않기때문에 0으로 만들어준다. 
            if(a[i][j] < 0) a[i][j] = 0;
        }
    }
    year++;
}
// 빙산의 영역의 개수를 구하기위한 DFS
void DFS(int r, int c){

    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];

        if(a[rr][cc] > 0 && ch[rr][cc] == false){
            ch[rr][cc] = true;
            DFS(rr,cc);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    cin >> R >> C;
    memset(a, -1, sizeof(a));
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            cin >> a[i][j];
        }
    }

    while(1){
        if(flag == true || landCnt > 1) break;
        
        
        memset(ch, false, sizeof(ch));
        afterOneYear();
        flag = true;
        landCnt = 0;
        
        for(int i=1; i<=R; i++){
            for(int j=1; j<=C; j++){
                if(a[i][j] > 0 && !ch[i][j]){
                    
                    ch[i][j] = true;
                    flag = false;            
                    DFS(i,j);
                    landCnt++;
                }
            }
        }
    }

    if(flag == true) cout << 0 << '\n';
    else cout << year << '\n';
    return 0;
}

소감

이 문제에 경우 빙산이 녹을경우 바다가 되는 것을 아는것이 매우 중요한 포인트이다. 그렇기 때문에 순차적으로 바다를 만들어주는것이 아니라, 먼저 빙산이 녹을 값을 구하고 이를 일괄적으로 빼주는 것이 중요했다.