문제

코드

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

int board[302][302];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int N,M;
bool checkTwice(){
    int vis[N][M],cnt=0;
    queue<pair<int,int>> cq;
    for(int i=0;i<N;i++) fill(vis[i], vis[i]+M, 0);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(vis[i][j] || board[i][j] == 0) continue;
            cq.push({i,j});
            vis[i][j] = 1;
            cnt++;
            while(!cq.empty())
            {
                auto cur = cq.front(); cq.pop();
                for(int dir=0;dir<4;dir++)
                {
                    int ny = cur.first + dy[dir];
                    int nx = cur.second + dx[dir];
                    if(ny < 0 || nx <0 || ny >=N || nx>= M) continue;
                    if(vis[ny][nx] || board[ny][nx] == 0) continue;
                    cq.push({ny,nx});
                    vis[ny][nx] = 1;
                }
            }
        }
    }
    if(cnt >= 2) return true;
    else return false;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int,int>> q;
    int day=0;
    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            cin >> board[i][j];
            if(board[i][j] > 0) q.push({i,j});
        }
    while(true)
    {
        day++;
        int temp[302][302];
        /* 임시 보드 temp에 board를 복사! */
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                temp[i][j] = board[i][j];
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(ny < 0 || nx <0 || ny >=N || nx>= M) continue;
                /* 비교는 board로 해야한다 */
                if(board[ny][nx] > 0) continue;
                /* 값 감소는 temp로 해야한다 */
                if(temp[cur.first][cur.second] >0) temp[cur.first][cur.second] -=1;
            }
        }
        /* 변경된 보드인 temp를 실제값인 board에 복사! */
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                board[i][j] = temp[i][j];
        /* 녹지 않은 빙하위치를 찾기 위한 과정 */
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                if(board[i][j] > 0) q.push({i,j});
        if(checkTwice()) break;
        if(q.size() == 0){
            day = 0;
            break;
        }
    }
    cout << day;
    return 0;
}

• key point!
  1) 빙하의 위치에서 4방을 검사하여 주변이 바다(0)인 것 만큼 감소!
  2) 감소하는 과정에서 실시간으로 값이 board에 반영되면 안된다
  --> 같은 해에 같이 녹는 빙하인데 만약 실시간 변경이 되버리면
  옆 빙하가 녹고 난 후 다음 빙하를 계산할 때 바다 면적이 늘어나버림!
  3) board를 복사하는 것이 핵심!