[ baekjoon ] #2573 빙산

백준 #2573 빙산

문제 요약

---

• 빙산의 높이 정보는 양의 정수로 저장
• 빙산 이외의 바다는 0으로 저장
• 1년마다 동서남북에 붙어있는 0의 개수만큼 줄어듦
• 두 덩어리 이상으로 분리되는 최초의 시간 구하기 !
• 전부 다 녹을 때까지 두 덩어리로 분리되지 않으면 0 출력

💡Idea

1. 빙산을 어떻게 녹일까?
   • 녹일 빙산(0이 아닌 곳)을 찾아 주변의 0 개수 만큼 녹이자 !
   • 이때 빙산의 높이가 음수면 나중에 바다로 처리되지 않으니 0으로 변경

[ Source Code ]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M; // 행, 열
int check[300][300];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우
queue <pair<int, int>> tmp;

// 동서남북의 0 개수 세고 빙산 녹이기
void remove_iceberg(int x, int y, vector<vector<int>> &iceberg) { 
    int zero = 0; // 0 개수
    for(int i=0; i<4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if(check[nx][ny]) continue;
        if(iceberg[nx][ny] == 0) {
            zero++;
        }
    }

    if(zero > 0) {
        iceberg[x][y] -= zero;
        if(iceberg[x][y] < 0) iceberg[x][y] = 0;
    }
}

// 연결된 빙산 개수 찾기
void count_iceberg(vector<vector<int>> iceberg) {
    while(!tmp.empty()) {
        int x = tmp.front().first;
        int y = tmp.front().second;
        tmp.pop();

        for(int i=0; i<4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(iceberg[nx][ny] == 0 || check[nx][ny]) continue;
            check[nx][ny] = 1;
            tmp.push({nx, ny});
        }
    }
}

int main() {
    // 1. 빙산 정보 입력 받기
    cin >> N >> M;
    vector <vector<int>> iceberg(N, vector<int>(M)); // 빙산
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> iceberg[i][j];
        }
    }

    int year = 0;

    while(1) {
        // 녹일 빙산 찾기
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(iceberg[i][j] != 0) { // 남아있다면
                    // 2. 빙산 녹이기
                    check[i][j] = 1;
                    remove_iceberg(i, j, iceberg);
                }
            }
        }

        fill(&check[0][0], &check[N][0], 0);
      
        // 3. 연결된 빙산 개수 세기
        int cnt = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(iceberg[i][j] != 0 && check[i][j] == 0) {
                    cnt++;
                    check[i][j] = 1;
                    tmp.push({i, j});
                    count_iceberg(iceberg);
                }
            }
        }

        year++;

        if(cnt >= 2) {
            cout << year << endl;
            exit(0);
        }
       
        if(cnt == 0) {
            cout << 0;
            exit(0);
        }
    }

    return 0;
}

Feedback

---

1. queue를 사용할 때 pop을 꼭 해줄 것 !
   → pop을 하지 않아 시간초과,,
2. 원본의 값을 변경해야할 때 인자에 & 꼭 붙여주기 !!
   → 이런 실수가 시간을 잡아먹는다 ㅠㅠ
3. 원래의 바다와 녹은 바다를 구분하는 부분에서 실수했다.

→ 전체적으로 실수를 너무 많이 한 것 같다. 너무 급하게 풀지 말고 천천히 생각해보며 실수 줄이기 !