[백준 20930번] [Union-Find / 스위핑] 우주 정거장

문제를 이리저리 돌려가면서 상황을 파악해가면 다음과 같은 상황임을 이해할 수 있다.

 

"우주 정거장의 x, y 좌표 사이에 다른 우주 정거장이 존재하면 이동할 수 있다."

 

그런데, 문제에서는 질문에서 주어진 우주 정거장 사이의 이동 가능 여부를 물어보고 있으므로 일종의 위의 명제의 참/거짓 여부의 연결 양상을 판단하라고 하는 것과 동치이다. 따라서 위 문제가 상호 배타적 집합임을 파악할 수 있다.

따라서 Union-Find로 문제를 풀어주면 된다.

 

이 문제의 경향성은 백준 17619번 개구리 점프와 매우 유사한 양상을 띄고 있다.

(viyoung.tistory.com/132)

다만, 이 문제에서는 x, y좌표를 모두 고려해야 하기 때문에 x기준으로 union, y기준으로 union을 시켜주면 된다.

 

추가적으로 스위핑하면서 union-find 하는 양상을 잘 보도록 하자.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef pair<int, int> pii;

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

    int find(int u){
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }// Path compression

    void merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return; // Already Merged;
        if(rank[u] < rank[v]) swap(u, v);
        parent[v] = u; // Union by rank
        if(rank[u] == rank[v]) rank[u]++;
        return;
    }
};

int main(void){
    fastio;
    int N, Q;
    cin >> N >> Q;
    vector<pair<pii, int> > path_x_store(N);
    vector<pair<pii, int> > path_y_store(N);
    DisjointSet world(N);
    for(int i = 0; i < N; i++){
        int sx, sy, fx, fy;
        cin >> sx >> sy >> fx >> fy;
        path_x_store[i] = make_pair(make_pair(min(fx, sx), max(fx, sx)), i);
        path_y_store[i] = make_pair(make_pair(min(fy, sy), max(fy, sy)), i);
    }

    sort(path_x_store.begin(), path_x_store.end());
    sort(path_y_store.begin(), path_y_store.end());

    for(int i = 0, j = 0; i < N; i = j){
        int end_point = path_x_store[i].first.second;
        while(j < N && end_point >= path_x_store[j].first.first){
            world.merge(path_x_store[i].second, path_x_store[j].second);
            end_point = max(end_point, path_x_store[j].first.second);
            j++;
        }
    }

    for(int i = 0, j = 0; i < N; i = j){
        int end_point = path_y_store[i].first.second;
        while(j < N && end_point >= path_y_store[j].first.first){
            world.merge(path_y_store[i].second, path_y_store[j].second);
            end_point = max(end_point, path_y_store[j].first.second);
            j++;
        }
    }

    for(int i = 0; i < Q; i++){
        int check1, check2;
        cin >> check1 >> check2;
        if(world.find(check1 - 1) == world.find(check2 - 1)){
               cout << 1 << "\n";
        }
        else cout << 0 << "\n";
    }

    return 0;
}