문제

• 2차원 배열, 높이 정보는 각 인덱스에 양의 정수로 저장
• 바다는 0
• 동서남북의 0의 개수만큼 본인의 높이에서 빼기
• 각 칸의 높이는 0보다 줄어들지 않음
• 한 덩어리 빙산이 주어질 때 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간을 구하시오

풀이

BFS 두개가 필요할 듯

• 빙산이 매년 녹는 것을 저장하는 Board[n][m], 해당 박스에 대한 bfs 돌림 돌릴 때마다 년++
• 빙산이 몇개인지 세는 bfs
• 다 녹을 때까지 두덩어리 이상으로 분리되지 않으면 0 출력
  - board가 모두 0이면 cout << 0
• bfs를 한번 돌릴때마다 빙산의 개수가 몇개인지 센 후 빙산의 상태 업데이트하기

풀이 1- 틀린 풀이 (board값의 갱신이 반영되는 풀이)

while(!Q.empty()){
                auto cur = Q.front();
                Q.pop();
                
                int amount=0;
                for(int dir=0; dir<4; dir++){ 
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    
                    //범위 걸어주기
                    if(nx<0||nx>n||ny<0||ny>m) continue;
                    if(board[nx][ny]==0) amount++; continue; //0의 개수 저장
                    if(vis[nx][ny]!=0) continue;
                    
                    vis[nx][ny]=1;
                    
                    Q.push({nx, ny});
                }
                board[cur.X][cur.Y]-=amount;
                
                
            }

원래는 한 칸에 대해 동서남북을 읽고 나면 0의 칸의 개수(amount)를 세어서 그 개수만큼을 해당 칸에서 빼는 형태로 하려 했는데, 이렇게 진행하면 한 칸이 진행될때마다 보드가 갱신이 되어서 인접해있는 칸의 빙산의 높이를 제대로 갱신할 수 없다는 문제점이 있다.
예를 들어

2높이의 빙산이 위, 왼쪽의 0의 칸의 개수에 따라서 0이 되어버리면 아래의 3높이의 빙산은 갱신된 값에 영향을 받아 3개를 빼, 높이가 0이 된다.

하지만 문제에서는 이렇게 갱신된 값이 아닌 원래 보드의 빙산의 높이만을 반영해야 한다.
따라서 1번의 풀이는 옳지 않다.

풀이 2 -

그러면 갱신된 값이 다음 칸의 높이를 계산하는 데 영향을 미치지 않게하려면 어떻게 해야할까?
만약 vis가 아닌 dist로 보드와 크기가 같은 판에 해당 노드의 상하좌우에 0이 몇개 존재하는지 저장하는 것은 어떨까?

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int board[1001][1001];
int dist[1001][1001]; //각 칸에 인접한 0의 개수를 저장하는 배열

int n, m, years, iceberg;
int dx[4] = { 1 , -1, 0, 0 };
int dy[4] = { 0 , 0, 1, -1 };


void printBoard(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << board[i][j]<< ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}


void printDist(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << dist[i][j]<< ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n>>m;
    
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> board[i][j];
    
    cout << "---------------------\n";
    
    //빙산 덩어리의 개수를 구함
    //빙산은 매년 상하좌우로 0의 개수만큼 녹음
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            //칸이 바다이거나 방문한 곳이거나 빙산 덩어리 개수가 2개 이상이면 pass
            if(board[i][j]==0 || dist[i][j]!=0) continue;
            //iceberg++; //빙산 덩어리 개수
            
            queue<pair<int, int>> Q;
            Q.push({i,j}); //1,1
            cout << i<<j<<".. \n";
            
            //dist에 갱신하기
            while(!Q.empty()){
                auto cur = Q.front(); //1,1
                Q.pop();
                
                int amount=0;
                for(int dir=0; dir<4; dir++){ 
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    
                    //범위 걸어주기
                    if(nx<0||nx>n||ny<0||ny>m) continue;
                    if(board[nx][ny]==0) {amount++; continue; }//0의 개수 저장
                    if(dist[nx][ny]!=0) continue;
                    
                    dist[nx][ny]=1;
                    Q.push({nx, ny});
                }
                dist[cur.X][cur.Y]= amount;
                printDist();
                
                
            }
        }
    }
    
    
    
    
    return 0;
}