백준 BOJ 17619 - 개구리 점프

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

17619번: 개구리 점프

스위핑 + 유니온파인드 문제

X 좌표가 서로 일부 겹치고 있다면 모종의 방법을 통해서 점프해 이동할 수 있기 때문에,

문제의 입력으로 들어오는 Y좌표와 지문의 조건

점프할 때 다른 통나무 위를 지나면 안된다.

를 무시할 수 있다.

이를 무시하고 x좌표만을 사용한 수직선들로 보면

겹치는 부분이 있는 선분들에 대해서 같은 그룹으로 묶어줘야 함을 알 수 있고,

이 그룹을 묶는데 유니온파인드를,

 

시간초과 없이 선분들을 선택하는 데에 스위핑을 사용해주면 문제를 해결할 수 있다.

 

50점짜리 입력범위가 큰 테스트케이스에 대해서

C++ 의 cin / cout 입력을 사용하면 시간초과를 받을 수 있는데,

부분 점수가 보장되는 문제라는 특성상 TLE가 뜨는것이 아니라

부분점수를 받게 되어서 시간초과임을 떠올리기가 쉽지 않다.

적어도 나는 그랬다 ㅠㅠ

cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

fastio를 사용해주도록 하자.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

struct pos{
	int x1;
	int x2;
	int idx;
};

bool cmp(pos &a, pos &b){
	if(a.x1 == b.x1) return a.x2 < b.x2;
	return a.x1 < b.x1;
}

int parent[123456] = {0};

vector<pos> v;

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

void joint(int a, int b){
	a = find(a);
	b = find(b);
	if(a != b){
		parent[a] = b;
	}
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	for(int i=0; i<123456; i++) parent[i] = i;
	
	int N,Q;
	int a,b,c;
	cin >> N >> Q;
	for(int i=1; i<=N; i++){
		cin >> a >> b >> c;
		v.push_back({a,b,i});
	}
	
	sort(v.begin(),v.end(),cmp);
	
	int s = v[0].x1;
	int e = v[0].x2;
	
	for(int i=1; i<N; i++){
		if(v[i].x1 <= e){
			joint(v[i].idx,v[i-1].idx);
			e = max(e, v[i].x2);
		}
		else{
			s = v[i].x1;
			e = v[i].x2;
		}
	}
	
	while(Q--){
		cin >> a >> b;
		if(find(a) == find(b)) cout << "1\n";
		else cout << "0\n";
	}
	return 0;
}