(C++) - 백준(BOJ) 2573번 : 빙산

www.acmicpc.net/problem/2573

2573번: 빙산

bfs로 푼 문제였습니다.

 

풀이방법

 1. bfs로 빙산 영역의 개수를 구할 수 있습니다. 빙산 영역의 개수가 1개 인동안 계속 년도를 증가시키면서 확인합니다. 

 

 2. loop를 도는 동안 얼음을 bfs로 녹입니다. 얼음이 있다면 근처 인접한 바다 영역의 개수를 구하고 기존 얼음이 있는 부분에서 바다 영역의 개수를 빼줍니다. 원본에서 미리 빼준다면 바다 영역의 개수를 정확히 구할 수 없기 때문에 copyBoard를 선언해 거기에 값을 저장하고 원본 배열인 board변수에 복사해줍니다.

 

 3. 얼음이 남아있다면 영역이 2개이상이므로 세준 년도를 출력합니다. 얼음이 다 녹았다면 0을 출력합니다. 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int board[301][301], copyBoard[301][301], ck[301][301];
int n, m, year;

int notMelt(){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(board[i][j]) return 1;
    return 0;
}

void meltIce(int i,int j){
    queue <pii> q;
    q.push({i,j});
    ck[i][j] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        copyBoard[x][y] = board[x][y];
        int zeroArea = 0;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >=n || 0 > ny || ny >= m) continue;
            if(ck[nx][ny]) continue;
            if(board[nx][ny]) {
                ck[nx][ny] = 1;
                q.push({nx,ny});
            }
            else zeroArea++;
        }
        if(copyBoard[x][y] - zeroArea >= 0) copyBoard[x][y] -= zeroArea;
        else copyBoard[x][y] = 0;
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            board[i][j] = copyBoard[i][j];
}

int getArea(){
    int ck[301][301] = {0};
    int area = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(board[i][j] && !ck[i][j]){
                area++;
                queue <pii> q;
                q.push({i,j});
                ck[i][j] = 1;
                while(!q.empty()){
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for(int i = 0 ; i < 4; i++){
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        if(0 > nx || nx >= n || 0 > ny || ny >= m) continue;
                        if(!board[nx][ny] || ck[nx][ny]) continue;
                        ck[nx][ny] = 1;
                        q.push({nx,ny});
                    }
                }
            }
        }
    }
    return area;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> board[i][j];
    int area = getArea();
    while(getArea() == 1){
        memset(ck,0,sizeof(ck));
        memset(copyBoard,0,sizeof(copyBoard));
        year++;
        for(int i = 0; i < n; i++)
            for(int j = 0 ; j < m; j++)
                if(board[i][j] && !ck[i][j])
                    meltIce(i,j);
    }

    if(notMelt()) cout << year << '\n';
    else cout << 0 << '\n';
}