백준 2573번 빙산 - C++ 풀이

---

 

1. 빙산 덩어리의 개수는 그래프의 연결 요소 개수이므로 DFS/BFS 호출 횟수와 같다.
2. 모든 빙산 칸에 대해 주변의 0의 개수만큼 높이를 줄여주고, 빙산덩어리의 개수를 센다.
3. 빙산 덩어리의 개수가 2개 이상이 될 때까지 2번 과정을 반복한다.

 

1. 빙산덩어리의 개수는 그래프의 연결 요소 개수이므로 DFS/BFS 호출 횟수와 같다.

 서로 연결되어 있는 빙산칸은 하나의 덩어리이므로, 빙산 덩어리의 개수는 그래프의 연결 요소 개수와 같다. 따라서 빙산 덩어리 개수는 모든 빙산칸을 방문하기까지 호출한 DFS/BFS의 횟수와 같다.

 

2. 모든 빙산 칸에 대해 주변의 0의 개수만큼 높이를 줄여주고, 빙산 덩어리의 개수를 센다.

 빙산이 녹는 과정을 시뮬레이션 해준 뒤, 빙산 덩어리의 개수를 세준다. 이때 주의할 점은 각 빙산칸의 높이를 순차적으로 낮추면 안 되고 동시에 낮춰야 한다는 점이다. 순차적으로 녹이면 주변의 0이 올해 0이 된 것인지, 작년부터 0이었던 것인지 구분할 수 없게 된다. 동시에 녹이기는 현재 상태 배열에 바로 결과를 저장하지 않고, 현재 배열을 보면서 별도의 배열에 녹인 후의 결과를 저장하는 것으로 구현할 수 있다.

 

3. 빙산 덩어리의 개수가 2개 이상이 될 때까지 2번 과정을 반복한다.

 빙산 덩어리의 개수가 2개 이상이 될 때까지 2번 과정을 반복하면 된다. 2번 과정에서 남은 빙산이 없는 경우에는 0을 출력한다.

반응형

---

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

const int MAX = 301, WATER = 0;

struct Ice {
    int r, c, h;
};

int N, M;
int board[MAX][MAX];
vector<Ice> ice;
bool visit[MAX][MAX];

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void DFS(int r, int c) {
    visit[r][c] = true;
    
    for (int i=0; i<4; i++) {
        int adjR = r + dr[i];
        int adjC = c + dc[i];
        
        if (visit[adjR][adjC] || board[adjR][adjC] == WATER) continue;
        
        DFS(adjR, adjC);
    }
}

// check(): 빙산 덩어리가 2개 이상인지 체크
bool check() {
    memset(visit, 0, sizeof(visit));
    
    bool dfs = false;
    for (auto x: ice) {
        if (visit[x.r][x.c] || x.h == 0) continue;
        if (dfs) return true;
        
        DFS(x.r, x.c);
        dfs = true;
    }
    
    return false;
}

// melt(idx): idx번째 빙산을 녹인다
void melt(int idx) {
    int r = ice[idx].r;
    int c = ice[idx].c;
    int h = ice[idx].h;
    
    for (int i=0; i<4; i++) {
        int adjR = r + dr[i];
        int adjC = c + dc[i];
        if (board[adjR][adjC] == WATER) h--;
    }
    
    ice[idx].h = max(0, h);
}

int simulate() {
    int ret = 1;
    
    while (true) {
        for (int i=0; i<ice.size(); i++) melt(i);
        
        bool finish = true;
        for (int i=0; i<ice.size(); i++) {
            int r = ice[i].r;
            int c = ice[i].c;
            int h = ice[i].h;
            board[r][c] = h;
            
            if (h > 0) finish = false;
        }
        
        if (check()) return ret;
        if (finish) return 0;
        
        ret++;
    }
    
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    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) ice.push_back({i, j, board[i][j]});
        }
    }
    
    cout << simulate();
    
    return 0;
}