백준 문제풀이 : (2573) 빙산 - C/C++

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

 

시간 제한	메모리 제한	난이도	알고리즘 분류
1초	256 MB	Gold 4	BFS

 

 

문제

 

 

풀이 

보자마자 bfs를 사용해야겠다고 생각하게되는 나름 직관적인 문제다. 하지만 풀이법이 대강 생각나도, 실제 구현하는 부분에서 자잘한 오류가 발생하는 등 어려움이 있었다.

 

막막함을 조금이라도 줄여보고자 문제 풀이를 글로 작성하는 것 부터 시작했다. 

 

1. 1년 후의 빙산 상태를 계산하여 저장한다.

2. 1년 후 빙산들이 두 조각 이상으로 분리되었는 지, 완전히 녹아 없어졌는 지, 아직 한 덩이인 상태인 지 체크한다.

3-1. 완전히 녹아 없어졌거나 두 조각 이상으로 분리되었다면 반복문을 탈출한다.

3-2. 아직 한 덩이인 상태라면 1-3번을 다시 실행한다.

4. 완전히 녹아 없어진 경우였다면 0을, 2조각 이상으로 분리된 상태였다면 그 조각 수를 출력한다.

 

1번과 2번 과정에서는 bfs를 사용했다. 1번의 경우 빙산이 남아있는 좌표들을 큐에 일괄 저장한 후, 하나씩 꺼내가며 임시 빙산 상태 배열에 새로 계산된 높이를 저장했다. 

 

큐에서 꺼낸 좌표의 상, 하, 좌, 우 칸을 조사하여 빙산의 수를 구한 후 '임시 빙산 배열[현재x좌표][현재y좌표] = 현재 빙산 배열[현재x좌표][현재y좌표]-(4-빙산의 수)' 공식으로 계산하면 현재 좌표의 빙산 높이에서 주변 바다 칸의 개수를 차감한 만큼의 값을 임시 빙산 배열에 저장할 수 있다.

 

더 자세한 내용은 아래 코드를 확인하는 편이 이해가 쉬울 것이다.

 

 

전체 코드

#include <iostream>
#include <deque>
#include <utility>
#include <cstring>

using namespace std;
int (*mInfo)[301]; //빙산 데이터 저장
deque<pair<int, int>> dq; //bfs 돌릴 큐
int check[301][301]; //방문 체크 배열
 
int xpos[] {-1, 0, 1, 0};
int ypos[] {0, 1, 0, -1};


void meltBFS(int N, int M) { //빙산을 년 단위로 녹이는 함수
    int newMount[301][301]; //임시 빙산 배열
    memset(newMount, 0, sizeof(newMount));
    
    for (int n=1 ; n<=N ; n++) {
        for (int m=1 ; m<=M ; m++) {
            if (mInfo[n][m]!=0) {
                dq.push_back(make_pair(n, m));
                check[n][m]=1;
            }
            
        }
    }

    while(!dq.empty()) {
        pair<int, int> cp = dq[0];
        dq.pop_front();
        
        int numOfmt=0;
        for (int p=0 ; p<sizeof(xpos)/sizeof(int) ; p++) {
            int nx=cp.first+xpos[p];
            int ny=cp.second+ypos[p];
            
            if (nx>=1 && nx<=N && ny>=1 && ny<=M && mInfo[nx][ny]>0) {
                if (check[nx][ny]==0) {
                    check[nx][ny]=1;
                }
                numOfmt++; //빙산의 수를 센다.
            }
        }
        
        newMount[cp.first][cp.second] = mInfo[cp.first][cp.second]-(4-numOfmt);  //4-빙산 칸의 수 = 바다 칸의 수
        if (newMount[cp.first][cp.second]<0) newMount[cp.first][cp.second]=0;
    }
    
    memcpy(mInfo, newMount, sizeof(newMount)); 
    //계산이 끝난 임시 빙산 배열 데이터를 현재 빙사 데이터에 덮어씌운다.
}


void checkBFS(int N, int M, int x, int y) { 
        
    dq.push_back(make_pair(x, y));
    
    while(!dq.empty()) {
        pair<int, int> cp = dq[0];
        dq.pop_front();
        
        for (int p=0 ; p<sizeof(xpos)/sizeof(int) ; p++) {
            int nx=cp.first+xpos[p];
            int ny=cp.second+ypos[p];
            
            if (nx>=1 && nx<=N && ny>=1 && ny<=M && mInfo[nx][ny]>0 && check[nx][ny]==0) {
                dq.push_back(make_pair(nx, ny));
                check[nx][ny]=1;
            }
        }
    }
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    
    int mount[301][301];
    for (int i=1 ; i<=N ; i++) {
        for (int j=1 ; j<=M ; j++) {
            scanf("%d", &mount[i][j]);
        }
    }    
    mInfo=mount;
    
    int year=0;
    int result=0;
    while(true) {
        memset(check, 0, sizeof(check));

        int numOfIce=0;
        for (int i=1 ; i<=N ; i++) { //빙산 그룹 개수 세는 반복문
            for (int j=1 ; j<=M ; j++) {
                if (mInfo[i][j]>0 && check[i][j]==0) {
                    check[i][j]==1;
                    checkBFS(N, M, i, j);
                    ++numOfIce; 
                }
            }
        }
        
        if (numOfIce==0) { result=0; break; } 
        else if (numOfIce>=2) { result=year; break; }
        
        
        memset(check, 0, sizeof(check));
        meltBFS(N, M);
    
        
        ++year;
    }
    
    printf("%d", result);
}

 

 

END.