[알고리즘 풀이 분석] BOJ 2573 빙산

오늘 매우 충격적인 사실을 알았다,,ㅋㅋㅋㅋㅜ
방금 BOJ 2573 빙산 문제를 풀었는데,, 메모리 초과 1번, 시간 초과를 한 11번 을 겪고 통과했다..! 근데 그 이유가 참,, 설마 설마 하던거라서,, 포스팅으로 남겨본다,,

BOJ 2573 빙산

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입출력

입출력은 언제나 꼼꼼하게 보자..^^

나의 풀이

이번 문제는 문제를 읽자 마자 알고리즘이 바로 생각난 경우였다. 알고리즘 자체를 설계하는데는 별로 오래 걸리지 않았고 메모리 초과, 시간 초과를 해결하는데 있어서 80% 이상의 시간을 투자해야 했던 문제이다.

알고리즘은 간단하다 빙산대륙 갯수를 구하고 + 빙산 녹이기

빙산 대륙 갯수 구하기

여기서 BFS 가 사용된다.

처음엔 지도의 모든 좌표를 돌면서 방문한 적이 없고 빙산이 있는 자리라면 BFS 를 시작함과 동시에 대륙 수를 count 하였다.

• 빙산 좌표만을 대상으로

하지만 문제 설명에서 '첫번째 행과 열 마지막 행과 열은 무조건 0' 이라고 하였고, 시간초과를 해결하는 과정에서 대륙의 수를 구하는 과정을 시작하기 전에 빙산이 있는 칸의 좌표만이 저장되는 배열 icePoints 을 대상으로만 대륙 구하기 BFS를 진행하였다.

• BFS와 동시에 주변의 바다인 칸을 미리 count

시간을 최대한 줄이기 위해서 BFS 탐색을 진행하면서 상하좌우로 빙산인 칸이 있는지를 체크할 때, 바다인칸 즉, 0인 칸이 몇개 있는지도 함께 체크 했다. 체크 후 해당 칸 좌표와 주변에 0인 칸이 몇개 인는지를 reference로 넘긴 배열 pointAndSea에 저장하였다.

이 과정에서 상하좌우를 살피는 부분을 따로 함수로 작성해 4번 도는 for문을 이용했었는데, 마지막까지 시간초과가 해결되지 않았을 때, 이 부분을 함수로 빼지 않고 4번의 if문으로 작성했더니 마침내 통과하였다,,!

(허무하긴 하지만,,, 그래도 시간적인 부분에서 신경써야 할 때 알아두고 사용하면 좋을 방법을 알았다! for문 < if 문 이 더 빠르군..)

또한 BFS에서 중복 방문을 피하기 위해선 반드시 queue 에서 좌표를 꺼낼 때가 아닌, queue 에 좌표를 넣을 때 방문 체크를 해야 하는 것을 추가적으로 수정하였다!

빙산 녹이기

위의 과정을 진행한 후 빙산 대륙의 수가 2이상이면 반복문을 종료하고 정답을 return 하고, 그렇지 않다면 빙산을 녹여야 한다!

이 과정을 비교적 간단하다.
위의 과정에서 구해 놓은 pointAndSea을 탐색하면서 map 값을 수정하고, 수정 뒤의 값이 0보다 작다면 0으로 수정해준다.

또 수정한 값이 여전히 0보다 크다면, 즉 아직 빙산인 칸이 남아 있다면 배열 icePoints 를 clear 한 뒤 해당 칸 좌표들을 다시 넣어주고, 이를 이용해 다시 빙산 대륙을 탐색하는 과정으로 돌아간다. 새롭게 완성된 배열 icePoints 의 사이즈가 0이면, 모든 칸이 바다인 즉, 빙산이 다 녹을 때 까지 대륙이 분리되지 않은 상황에 해당하므로 0을 return 하고 실행을 종료한다!

이부분에서 실수한 사람들이 많았던 것 같고 나역시 그랬다..! 문제를 똑바로 읽자..ㅎ

코드

#include <iostream>
#include <vector>
#include <queue>

// BOJ 2573 빙산, BFS 골드 4, 시간초과 해결 개오래걸림,,,ㅋㅋ
using namespace std;

int N, M;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void BFS(int y, int x, vector<vector<int>> map, vector<vector<bool>> & visited, vector<pair<pair<int, int>, int>> & pointAndSea){
    queue<pair<int, int>> points;

    points.push(make_pair(y, x));
    visited[y][x] = true;

    while (!points.empty()){
        pair<int, int> location = points.front();
        points.pop();

        int sea = 0;
        
        // 상하 좌우 탐색 -> for 보다 4번의 if 문이 빠름 
        if (map[location.first + dy[0]][location.second + dx[0]] == 0) sea++;
        if (map[location.first + dy[1]][location.second + dx[1]] == 0) sea++;
        if (map[location.first + dy[2]][location.second + dx[2]] == 0) sea++;
        if (map[location.first + dy[3]][location.second + dx[3]] == 0) sea++;

        pointAndSea.push_back(make_pair(location, sea));

        for (int i = 0; i < 4; ++i) {
            int row = location.first + dy[i];
            int col = location.second + dx[i];

            if (map[row][col] > 0 && !visited[row][col]){
                // 반드시 큐에 좌표를 넣을 때 방문 체크 해야 중복 방문을 방지 
                visited[row][col] = true;
                points.push(make_pair(row, col));
            }
        }
    }
}

int getMinYears(vector<vector<int>> map, vector<pair<int, int>> icePoints){
    int years = 0;

    while (icePoints.size() > 0){
        vector<vector<bool>> visited(N, vector<bool>(M, false));

        // 덩어리 갯수 확인
        int continent = 0;
        vector<pair<pair<int, int>, int>> pointAndSea;  // 빙산 칸 별로 주변의 바다칸 수가 저장될 배열 
        
        for (int i = 0; i < icePoints.size(); ++i) {
            if (!visited[icePoints[i].first][icePoints[i].second]){
                continent++;
                BFS(icePoints[i].first, icePoints[i].second, map, visited, pointAndSea);
            }
        }

        // 덩어리가 2개 이상이면 종료
        if (continent >= 2) break;

        // 빙산 녹이기
        years++;
        
        icePoints.clear();  // 새롭게 빙산 위치를 담을 배열 초기화 
        for (int i = 0; i < pointAndSea.size(); ++i) {

            // map 값 수정, 0보다 작아지면 0으로 수정 
            if (map[pointAndSea[i].first.first][pointAndSea[i].first.second] < pointAndSea[i].second){
                map[pointAndSea[i].first.first][pointAndSea[i].first.second] = 0;
            }
            else map[pointAndSea[i].first.first][pointAndSea[i].first.second] -= pointAndSea[i].second;

            // 수정된 칸이 여전히 빙산이라면 새롭게 탐색할 배열로 
            if (map[pointAndSea[i].first.first][pointAndSea[i].first.second] > 0){
                icePoints.push_back(make_pair(pointAndSea[i].first.first, pointAndSea[i].first.second));
            }
        }

        // 모든 빙사이 녹을 때 까지 대륙이 분리되지 않은 경우 
        if (icePoints.size() == 0 ){
            years = 0;
            break;
        }

    }

    return years;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>N>>M;

    vector<vector<int>> map(N, vector<int>(M));
    vector<pair<int, int>> icePoints;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin>>map[i][j];
            if (map[i][j] > 0){
                icePoints.push_back(make_pair(i,j));
            }
        }
    }

    int answer = getMinYears(map, icePoints);
    cout<<answer;

    return 0;
}

그래도 시험 전에 이런 팁을 얻을 수 있었으니..! 잘했다..!