KOI 2019 중등부 2차 / 개구리 점프 - 17619

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, Q;
 
struct disjointSet {
 
    vector<int> parent, rank;
 
    disjointSet(int n) : parent(n), rank(n, 0) {
        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]);
    }
 
    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if(u == v) return;
        if(rank[u] < rank[v]) swap(u, v);
        parent[v] = u;
        if(rank[u] == rank[v]) rank[u]++;
    }
};
 
struct node {
    int s;
    int e;
    int idx;
};
 
bool operator<(node& n1, node& n2) {
    return n1.s < n2.s;
}
 
node arr[100000];
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> Q;
    disjointSet set(N);
    int x1, x2, y;
    for(int i = 0; i<N; ++i) {
        cin >> x1 >> x2 >> y;
        arr[i] = {x1, x2, i};
    }
    sort(arr, arr+N);
    int E = arr[0].e;
    for(int i = 0; i<N-1; ++i) {
        if(E >= arr[i+1].s) {
            set.merge(arr[i].idx, arr[i+1].idx);
            E = max(E, arr[i+1].e);
        } else E = arr[i+1].e;
    }
    for(int i = 0; i<Q; ++i) {
        cin >> x1 >> x2;
        x1 = set.find(x1-1);
        x2 = set.find(x2-1);
        if(x1 == x2) cout << 1;
        else cout << 0;
        cout << "\n";
    }
}

 

 

 

 

 

https://www.acmicpc.net/problem/17619

17619번: 개구리 점프

 

 

 

 

 

개구리 점프

통나무들을 x축 위에 나열했을때, x값들이 끊기지 않고 연속적인 값이면, 그 안에 해당되는 통나무끼리 서로 이동이 가능합니다.

따라서 통나무를 표현하는 구조체를 선언하고 해당 구조체 배열에 통나무들을 모두 넣어준다음, 통나무 시작점을 기준으로 sort해주게 되면, 통나무들 끼리의 이어짐 여부를 쉽게 확인할 수 있습니다.

union-find를 이용해서 이어져 있는 통나무 끼리 합쳐주면 서로 다른 두 통나무가 이어져있는지 아닌지 빠른 시간안에 알아낼 수 있습니다.