[백준/C++] 2573번 빙산

문제: www.acmicpc.net/problem/2573

2573번: 빙산

 

 

문제풀이

 

BFS로 주변 바다 블록의 개수를 세어서 바다 블록의 수만큼 현재 높이에서 뺀 후 board에 갱신하는 방식으로 문제를 풀었다.

 

처음 풀 땐 빙하의 최대 높이가 10이기 때문에 10년안에 모든 빙하가 녹을 것이라고 생각해서 1~10년을 brute-force 했었다. 하지만 다음 그림과 같은 반례가 있기 때문에 빙하가 녹는 기간은 10년을 훌쩍 넘을 수 있다. 때문에 빙하가 두 덩이가 되거나 다 녹을 때까지 무한루프를 사용했다.

 

반례)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0

0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0

0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0

0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0

0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int visited[300][300] = {0,};
int board[300][300];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    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 = -1;
    queue<pair<int,int>> q;
    while(1){
        year++;
        int area = 0;
        bool flag = true; //빙하가 모두 녹았는지 확인

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(visited[i][j] || board[i][j] == 0) continue;

                q.push({i,j});
                visited[i][j] = 1;
                area++;
                flag = false;

                if(area == 2){ //구역이 두개가 되면
                    cout<<year;
                    return 0;
                }

                while (!q.empty()){   
                    pair<int,int> cur = q.front();
                    q.pop();
                    int sea = 0;

                    for(int dir=0; dir<4; dir++){
                        int nx = cur.first + dx[dir];
                        int ny = cur.second + dy[dir];

                        if(nx<0||nx>=n||ny<0||ny>=m) continue;
                        if(visited[nx][ny]) continue;

                        if(board[nx][ny]){
                            q.push({nx,ny});
                            visited[nx][ny] = 1;
                        }
                        else
                            sea++;
                    }
                    board[cur.first][cur.second] -= sea;

                    if(board[cur.first][cur.second] < 0) //빙하 높이는 0이 최소이다.
                        board[cur.first][cur.second] = 0;
                }
            }
        }

        if(flag){ //빙하가 모두 녹았으면 0 출력
            cout<<0;
            return 0;
        }

        for(int i=0; i<n; i++)
            fill(visited[i], visited[i]+m, 0);
    }
}

 

 

결과