[C++] BAEKJOON 2573 빙산

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

2573번: 빙산

dfs 를 이용하여 문제를 해결하였습니다.

• 매 년 마다 dfs 를 순회하여 빙산을 없애줍니다.
• 빙산을 한 번에 없애면 같은 년도에 먼저 없어진 빙산이 주변 빙산에 영향을 주므로 temp 배열을 선언해 얼마나 없애햐 할지 기억한 후, 한 번에 없애주도록 합니다.
• 같은 년도에 dfs 가 두 번 발생했다면, 빙산이 나눠져 있는 것이므로 종료합니다.
• dfs가 한 번도 발생하지 않았다면 빙산이 모두 녹은 것이므로 종료합니다.

#include <iostream>
#include <cstring>

using namespace std;

int board[301][301];
int temp[301][301];
int visited[301][301];

int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};

void dfs(int r,int c,int N,int M){
    // 방문 체크
    visited[r][c] = 1;
    // 빙하를 하나씩 녹이면 이에 다른 빙하가 영향을 받으므로 얼만큼 녹는지 기억했다가 한꺼번에 녹인다.
    for (int i=0;i<4;i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (0<=nr && nr<N && 0<=nc && nc<=M){
            if(board[nr][nc] == 0){
                temp[r][c]--;
            }
        }
    }
    
    for (int i=0;i<4;i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (0<=nr && nr<N && 0<=nc && nc<=M){
            if (board[nr][nc]&&!visited[nr][nc]){
                dfs(nr,nc,N,M);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    
    int N,M;
    cin >> N >> M;
    
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++){
            cin >> board[i][j];
        }
    }
    
    int year = 0;

    while (1){
        memset(visited, 0, sizeof(visited));
        memset(temp, 0, sizeof(temp));
       
        
        int dfs_count = 0;
        int dfs_flag = 0;
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (board[i][j]!=0 && !visited[i][j]){
                    dfs(i,j,N,M);
                    dfs_count++;
                    if (dfs_count == 2) {
                        dfs_flag = 1;
                        break;
                    }
                }
            }
            if (dfs_flag) break;
        }
        if (dfs_flag) break;
        
        // 빙하가 모두 녹은 경우
        if (dfs_count == 0){
           year = 0;
            break;
        }
            
        
        // 빙하를 한 번에 녹이기
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                board[i][j] += temp[i][j];
                if (board[i][j] < 0) board[i][j] = 0;
            }
        }
        
        year++;
    }
    cout << year << "\n";
    
    return 0;
}