[백준] 2573번 빙산 C++ 코드

코드

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 303;
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,1,-1};
int n,m,a[MAX_N][MAX_N],b[MAX_N][MAX_N],visited[MAX_N][MAX_N],res;

// 덩어리 판단 로직
void dfs(int x, int y) {
    visited[x][y] = 1;
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= n || ny >= m || nx < 0 || ny < 0) continue;
        if(!visited[nx][ny] && a[nx][ny]) {
            dfs(nx,ny);
        }
    }
}

// 유효여부 판단 로직
bool check() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(a[i][j]) return true;
        }
    }
    return false;
}

// 빙산 녹이기 로직
void melting() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            int cnt = 0;
            if(!a[i][j]) b[i][j] = a[i][j];
            else {
                for(int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx >= n || ny >= m || nx < 0 || ny < 0) continue;
                    if(a[nx][ny] == 0) cnt++;
                }
                b[i][j] = max(0, a[i][j] - cnt); // 0보다 작아지면 안됨
            }
        }
    }
    memcpy(a,b, sizeof(a)); // 한 번에 업데이트
}
// 한 덩어리가 주어진다고 했으므로 처음부터 한 덩어리인 케이스는 고려 X
// 덩어리 판단하는 로직 1개
// 녹는 로직 1개
// 맵 유효성 로직 1개
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 >> a[i][j];
        }
    }
    // 녹이고, 개수 확인
    res = 0;
    while(1) {
    	// 종료되지 않은 상태에서, 더 이상 녹일 빙산이 없는 경우
        if(!check()) {
            res = 0;
            break;
        }
        int cnt = 0; // 섬 개수
        melting();
        res++;
        fill(&visited[0][0], &visited[0][0] + MAX_N*MAX_N, 0);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(a[i][j] && !visited[i][j]) {
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        if(cnt > 1) break;
    }
    cout << res << '\n';
    return 0;
}

풀이

바다가 있고, 바다에 접한 칸 만큼 빙산을 녹이는 문제이다. 빙산을 녹일 때 주의해야할 점은, 녹이자마자 바로 맵에 반영하면 잘못된 값이 나올 수 있다는 것이다. 이를테면 원래 2면에 접하고 있었던 얼음이 있다. 해당 빙산은 -2를 해주어야 하지만 위에 빙산이 녹았다는 게 바로 반영이 되면 3면을 바다로 인식해 -3이 될 수 있다. 이 점을 주의해서 따로 맵을 만들어두고 한 번에 반영해야한다. 이 점만 주의하면 빙산을 녹이는 로직을 작성할 수 있다.

 

빙산의 개수를 구해주는 로직은 일반 dfs를 사용했다. 그리고 맵의 유효성 또한 매번 확인해주었다. 만약 개수가 나오지 않았는데 모든 빙산이 녹았다면 res를 0으로 변경하고 반복문을 종료한다. 섬의 개수가 2개 이상인 경우에는 res를 출력하도록 했다.