17619번 개구리 점프

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

union find 백준 boj KOI 한국정보올림피아드 2019 2차 중등부 복습 코딩테스트 집합 코테 필수 추천

하나의 그룹에 속해있는지 판단할 수 있는지의 여부를 묻는 문제이다.

Union - Find를 활용하면 된다.

다른 방법으로는 정렬 후 하나의 선분을 늘려간다는 생각으로 구현하면 된다.

예) x = 0부터 시작하여 v에서 하나씩 꺼내어 비교한 후 x를 늘리는 방법

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 100002
 
typedef struct info
{
    int x1, x2, num;
};
 
int N, Q, p[Max];
vector<info> v;
 
bool cmp(const info & a, const info & b)
{
    return a.x1 < b.x1;
}
 
int Find(int x)
{
    if (x == p[x]) return x;
    return p[x] = Find(p[x]);
}
 
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
 
    if (a < b) {
        p[b] = a;
    }
    else {
        p[a] = b;
    }
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\input.txt", "r", stdin);
    cin.tie(0);
 
    scanf("%d %d", &N, &Q);
 
    int x1, x2, y;
    for (int i = 1; i <= N; i++) {
        scanf("%d %d %d", &x1, &x2, &y);
        v.push_back({ x1, x2, i });
        p[i] = i;
    }
 
    sort(v.begin(), v.end(), cmp);
 
    // for(int i=0; i<N; i++) for(int j=i+1; j<N; j++)으로 해도 된다.
    // 단, 위의 경우에도 v[i].num과 v[j].num을 비교하여 break를 적절하게 사용하면 된다.
    for (int i = 0, j = 1; i < N && j < N;) {
        if (v[j].x1 <= v[i].x2) {
            Union(v[i].num, v[j].num);
            ++j;
        }
        else {
            ++i;
        }
    }
 
    int f, t;
    for (int i = 0; i < Q; i++) {
        scanf("%d %d", &f, &t);
        if (Find(f) == Find(t)) {
            printf("1\n");
        }
        else {
            printf("0\n");
        }
    }
 
    return 0;
}