[BOJ 2573] 빙산

2573번: 빙산

 

1. 문제 설명

2. 구현 아이디어 1 - 틀렸습니다

문제를 풀면서 덩어리가 몇 개인지 구해야 한다는 점에서 BFS/DFS 문제임을 알 수 있었다.

위 사진에서 높이가 2인 빙산이 녹으면서 0이 되고, 높이가 4인 빙산은 2가 되었다.

모든 빙산은 다 같이 줄어드는 것이기 때문에 높이가 4인 빙산 주변의 0인 칸을 셀 때 2→0인 빙산이 포함되지 않도록 주의해야 한다 !!

 

문제를 풀기 위해 아래와 같은 풀이 과정을 떠올렸다.

1. 입력을 받으면서 빙산의 좌표를 iceberg라는 배열에 저장하자
2. 덩어리가 두 덩어리 이상으로 분리되지 않고, 모든 빙산이 녹지 않을 때까지 반복문을 돌며 각 빙산이 얼마나 녹을지 계산한다.
3. 위에서 말한 점을 주의하기 위해 녹을 빙산의 높이를 다른 배열에 저장했다가 반복문을 1번 더 돌며 빙산을 녹인다.

 

이를 코드로 구현하면 아래와 같다.

2+3번 과정을 하나의 반복문에서 진행할 경우 앞선 빙산의 높이가 0이 된 것이 다음 빙산을 녹일 때 영향을 미치기 때문에 반복문을 2개로 분리하였다. 그리고 3번 과정에서 녹을 빙산의 높이는 map 자료 구조를 사용하여 저장해두었다.

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

int n, m;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int cx, cy, nx, ny;

// 빙산 덩어리를 세는 함수
int countGroup(vector<vector<int>> &board, vector<pair<int, int>> iceberg) {
    int group = 0;

    vector<vector<int>> visited = vector(n, vector<int>(m));

    for (auto ice : iceberg) {
        if (visited[ice.X][ice.Y]) continue;

        stack<pair<int, int>> s;
        s.push({ice.X, ice.Y});
        visited[ice.X][ice.Y] = true;

        while (!s.empty()) {
            cx = s.top().X;
            cy = s.top().Y;
            s.pop();

            for (int i = 0; i < 4; ++i) {
                nx = cx + dx[i];
                ny = cy + dy[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (board[nx][ny] == 0 || visited[nx][ny]) continue;
                s.push({nx, ny});
                visited[nx][ny] = true;
            }
        }
        group++;
    }

    return group;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    // 2차원 배열
    vector<vector<int>> board = vector(n, vector<int>(m));
    // 빙산의 좌표 저장
    vector<pair<int, int>> iceberg;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> board[i][j];

            if (board[i][j] != 0) iceberg.push_back({i, j});
        }
    }

    // 두 덩어리 이상으로 분리되는 최초의 시간(=정답)을 저장할 변수
    int time = 0;
    
    // 덩어리가 하나이고, 아직 빙산이 남아있을 경우
    while (countGroup(board, iceberg) == 1 && !iceberg.empty()) {
        // 인접한 네 방향 중 0인 칸의 개수를 세고 cnt에 저장
        // 빙산을 한번에 녹이기 위해 map에 저장해둠
        map<pair<int, int>, int> mp;
        for (auto ice : iceberg) {
            int cnt = 0;
            
            cx = ice.X;
            cy = ice.Y;
            for (int i = 0; i < 4; ++i) {
                nx = cx + dx[i];
                ny = cy + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (board[nx][ny] == 0) cnt ++;
            }

            mp[{cx, cy}] = cnt;
        }

        // 앞서 계산한 높이만큼 빙산을 녹인다
        for (auto elem : mp) {
            board[elem.first.X][elem.first.Y] -= mp[{elem.first.X, elem.first.Y}];
            // 결과가 음수일 경우 0으로 갱신
            if (board[elem.first.X][elem.first.Y] < 0) board[elem.first.X][elem.first.Y] = 0;
        }
        
        // 높이가 0이 되면 빙산 좌표 배열에서 삭제
        for (int i = 0; i < iceberg.size(); ++i) {
            if (board[iceberg[i].X][iceberg[i].Y] == 0) iceberg.erase(iceberg.begin()+i);
        }

        time++;
    }
    
    // 두 덩어리 이상으로 분리된 경우
    if (countGroup(board, iceberg) > 1) cout << time << "\n";
    // 빙산이 다 녹을 때까지 분리되지 않을 경우
    else cout << 0 << "\n";

    return 0;
}

 

3. 구현 아이디어 2 - 맞았습니다 !!

질문 게시판을 통해 아래 블로그에서 반례를 찾을 수 있었다.

[c++] 백준 빙산(2573), BFS, 반례모음

 

5 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0

0

 

위와 같은 입력에서는 1년 뒤 전부 녹기 때문에, 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으므로 0이 정답이지만 나의 코드는 1이 출력되었다.

디버깅을 진행해본 결과 아래와 같이 빙산 좌표 배열을 삭제하는 코드가 잘못된 것을 알 수 있었다.

// 높이가 0이 되면 빙산 좌표 배열에서 삭제
for (int i = 0; i < iceberg.size(); ++i) {
    if (board[iceberg[i].X][iceberg[i].Y] == 0) iceberg.erase(iceberg.begin()+i);
}

 

erase 함수는 지우고 싶은 원소의 index를 인자로 넘겨 vector에서 해당 원소를 지우는 함수이다.

원소를 지우면서 생긴 빈 칸을 채우기 위해 원소들이 한 칸씩 shift된다.

 

그렇기 때문에 반복문을 돌 때마다 원소들의 index는 변하여 원하지 않은 결과가 나올 수 있는 것이다.

 

원소를 직접 지우는 함수를 사용하지 못하기 때문에 그래프 문제에서 visited 배열을 쓰는 것과 유사하게 melt라는 boolean 배열을 만들어 높이가 0인 i번째 빙산은 melt[i] = true가 되도록 저장하였다.

 

아래와 같이 iceberg 배열이 비었는지 체크하는 것을 melt 배열을 사용하여 확인하도록 코드를 변경하여 문제를 해결할 수 있었다.

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

int n, m;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int cx, cy, nx, ny;

// 중략 ...

// 모든 빙산이 녹았으면 true를 반환
bool allMelt(vector<bool> &melt) {
    for (auto elem : melt) {
        if (!elem) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    // 중략 ...
    // while문 조건을 allMelt 함수를 사용하도록 변경 
    while (countGroup(board, iceberg, melt) == 1 && !allMelt(melt)) {
        map<pair<int, int>, int> mp;
        for (int i = 0; i < iceberg.size(); ++i) {
            pair<int, int> ice = iceberg[i];
            // 이미 녹은 빙산은 고려할 필요가 없으니 skip
            if (melt[i]) continue;

            // 중략 ...
        }

        // 중략 ...
        // 높이가 0이 되면 빙산 좌표 배열에서 삭제
        for (int i = 0; i < iceberg.size(); ++i) {
            if (board[iceberg[i].X][iceberg[i].Y] == 0) melt[i] = true;
        }

        time++;
    }

    if (countGroup(board, iceberg, melt) > 1) cout << time << "\n";
    else cout << 0 << "\n";

    return 0;
}

 

 

처음에는 코드에 반복문이 너무 많은 것 같아서 시간 초과가 날까 걱정했지만 2차원 배열의 최대 칸이 300 * 300 = 90,000칸이고, 빙산의 최대 갯수는 10,000개이기 때문에 시간 초과가 발생하지 않고 문제를 풀 수 있었다 !