[BOJ/백준][Gold3] 17619 : 개구리 점프 (C++)

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

17619번: 개구리 점프

 

[난이도] Gold3
[유형] 스위핑

[풀이]
일단 좌측 x값을 기준으로 정렬을 한다.
y와 관계없이 (xi1,xi2) (xj1,xj2)가 이동 가능한 점이려면
x12>=xj1 를 만족하면 된다.
즉, y와 상관없이 연속된 직선상에 포함되는 점들은 이동이 가능한 점(집합)이다.

스위핑을 해주면서 어떤 그룹에 속하는지 배열에 저장하면 답을 찾을 수 있다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int N,Q;
struct P{
    int x1,x2,num;
};
bool cmp(P a,P b){
    return a.x1 < b.x1;
}
P tree[100001];
int g[100001];
int main(){
    scanf("%d%d",&N,&Q);
    for(int i=0;i<N;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        tree[i]={a,b,i};
    }
    sort(tree,tree+N,cmp);

    int sid=0,e=tree[0].x2;
    g[0]=sid;

    for(int i=1;i<N;i++){
        if(tree[i].x1<=e){
            if(tree[i].x2>e) e=tree[i].x2;    
        }else{
            sid++;
            e=tree[i].x2;
        }
        g[tree[i].num]=sid;
    }
    while(Q--){
        int u,v;
        scanf("%d%d",&u,&v);
        u--,v--;
        if(g[u]==g[v]) puts("1");
        else puts("0");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/17619.cpp