[백준 14868번] [Union-Find] 문명

사실 아이디어는 잘 잡았는데, 구현 실력이 모자라서 시간 초과 및 메모리 초과가 나서 인터넷에서 풀이를 많이 참고하였다.

 

일단 처음에 들었던 생각은 다음과 같다.

 

문명이 몇개인지 알아야하고, 각 문명별로 컨트롤 해야하는 상황이므로 Union-Find 방법을 생각하였다.

결과적으로 그룹에 속하는지 속하지 않는지를 빠르게 판단할 수 있어야하고, 그 결합도 쉬워야하기 때문이다.

(예를 들어 그룹끼리 합쳐질 때 만약 Union-Find를 사용하지 않는다면 일일히 방문하여 집합 정보에 대한 내용을 수정해주어야 하는데 이 경우에는 시간 초과가 날 수 밖에 없다.)

 

여기까지는 참 좋았는데, 2중 Union-Find를 진행하여 메모리 손실이 많이 발생하였다.

즉, pair<int, int> parent[2001][2001]로 잡고 default를 parnet[i][j].= make_pair(i, j)로 설정하였다.

그리고 union될 때 마다 pair값을 저장한 DisjointSet을 갱신하는 방향으로 진행하였다.

 

물론 가능한 방향이기는한데, 시간적 측면이나 메모리 측면에서 매우 비효율적이다.

 

사실 생각해보면, 중요한 것은 문명이 합쳐지는 것의 여부이므로 문명끼리만 Union-Tree를 형성해주면 된다.

즉, vector<int> parent(1001)로도 충분하다.

 

또한 추가적으로 queue를 잡아서 재귀적으로 돌리는 방향성에 대해서도 잘 알아두도록 하자.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int map[2001][2001];
int N, M;

struct DisjointSet{
    vector<int> parent, rank;
    DisjointSet() : parent(100001), rank(100001, 1){
        for(int i = 1; i < 100001; i++){
            parent[i] = i;
        }
    }

    int find(int n){
        if(n == parent[n]) return n;
        else return parent[n] = find(parent[n]);
    }

    void merge(int n, int m){
        n = find(n); m = find(m);
        if(n == m) return;
        if(rank[n] < rank[m]) swap(n, m);
        parent[m] = n;
        if(rank[n] == rank[m]) rank[n]++;
        return;
    }
};

int move_num[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool intheSpace(pair<int, int> data){
    if(1 <= data.first && data.first <= N && 
       1 <= data.second && data.second <= N) return true;
    else return false;
}

DisjointSet world;
queue<pair<int, int> > joint_set;
queue<pair<int, int> > progress_set;

void joint(){
    while(joint_set.size()!= 0){
        int x = joint_set.front().first;
        int y = joint_set.front().second;
        progress_set.push(joint_set.front());
        joint_set.pop();
        for(int i = 0; i < 4; i++){
            int dx = x + move_num[i][0];
            int dy = y + move_num[i][1];
            if(!intheSpace(make_pair(dx, dy))) continue; // 범위 바깥에 있는 경우
            if(map[dx][dy] != 0 && (world.find(map[x][y]) != world.find(map[dx][dy]))){
                world.merge(map[x][y], map[dx][dy]);
                M--;
            } 

        }
    }
    return;
}

void progress(){
    while(progress_set.size() != 0){
        int x = progress_set.front().first;
        int y = progress_set.front().second;
        progress_set.pop();
        for(int i = 0; i < 4; i++){
            int dx = x + move_num[i][0];
            int dy = y + move_num[i][1];
            if(!intheSpace(make_pair(dx, dy))) continue;
            // 진영이 없는 경우
            if(map[dx][dy] == 0){
                map[dx][dy] = map[x][y];
                joint_set.push(make_pair(dx, dy));
            }
            // 진영이 있는데 지금 현재 상태랑 다른 경우
            if(map[dx][dy] != 0 && world.find(map[x][y]) != world.find(map[dx][dy])){
                world.merge(map[x][y], map[dx][dy]);
                M--;
            }
        }
    }
    return;
}

int main(void){
    cin >> N >> M;

    memset(map, 0, sizeof(map));

    for(int i = 0; i < M; i++){
        int temp1, temp2;
        cin >> temp1 >> temp2;
        map[temp1][temp2] = i + 1;
        joint_set.push(make_pair(temp1, temp2));
    }

    int count = 0;

    while(M > 1){
        joint();
        if(M == 1){
            cout << count << "\n";
            return 0;
        }
        progress();
        count++;
    }

    cout << count << "\n";
    return 0; 
}