[BOJ]2573 빙산

• sol1: BFS 풀이 = 코드의 파트를 나누고, 파트별로 구현하는 것이 중요

1. 모두 녹을 때까지 반복
   1-1. BFS를 통해 빙산 개수 카운트(빙산의 개수가 2개 이상이면 정답 도출)
   1-2. 년도 증가
   1-3. 빙하 melting 수행: 물과 맞닿은 부분에 대해 적용
   1-4. 다음 반복을 위해 초기화

#include <bits/stdc++.h>
using namespace std;
int N, M;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vector<int>> board(301, vector<int>(301, 0));
vector<vector<bool>> visited(301, vector<bool>(301, false));
bool all_melt(){
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            if(board[i][j] != 0){
                return false;
            }
        }
    }
    return true;
}
void bfs(int x, int y){
    queue<pair<int, int>> que;
    visited[x][y] = true;
    que.push({x, y});
    while(!que.empty()){
        pair<int, int> cur = que.front();
        que.pop();
        for(int i = 0; i < 4; ++i){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(visited[nx][ny] || board[nx][ny] == 0) continue;
            visited[nx][ny] = true;
            que.push({nx, ny});
        }
    }
}
int main(){
    int year = 0;
    bool trigger = false;
    cin >> N >> M;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < M; ++j)
            cin >> board[i][j];
    while(!all_melt()){
        //BFS 체크
        int part = 0;
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < M; ++j){
                if(board[i][j] != 0 && !visited[i][j]) { 
                    ++part;
                    bfs(i, j);
                    if(part >= 2) {
                        trigger = true;
                        break;
                    }
                }
            }
            if(trigger) break;
        }
        if(trigger) break;
        year++;//년도 증가
        //빙하 감소
        vector<vector<int>> mcnt(N, vector<int>(M, 0));
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < M; ++j){
                if(board[i][j] > 0) {
                    int cnt = 0;
                    for(int k = 0; k < 4; ++k) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if(board[nx][ny] == 0) ++cnt;
                    }
                    mcnt[i][j] = cnt;
                }
            }
        }
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < M; ++j){
                board[i][j] = max(board[i][j] - mcnt[i][j], 0);
            }
        }
        //배열 초기화
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < M; ++j)
                visited[i][j] = false;
    }
    if(trigger) cout << year;
    else cout << 0;
    return 0;
}