[BOJ 17619 // C++] 개구리 점프

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17619번 문제인 개구리 점프이다.
문제는 아래 링크를 확인하자.

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

17619번: 개구리 점프

주어진 통나무들을 왼쪽 끝 좌표 순서대로 먼저 정렬하자. 그리고 차례대로 읽어나가면서 이번 통나무가 이전에 등장한 통나무와 겹치는지를 확인해나가자. 이 때 매 차례마다 그 때까지 확인한 통나무의 오른쪽 끝이 어디인지를 기록해나가면 이전에 등장한 통나무와 겹치는지를 쉽게 확인할 수 있다.

 

이제 겹치는 통나무들 사이의 관계를 집합으로 생각해 주어진 문제를 disjoint set 자료구조를 이용해 간단하게 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int arr[100001];

int findf(int x) {
	if (x == arr[x]) return x;
	return arr[x] = findf(arr[x]);
}

int N, Q;
pair<pair<int, int>, int> logs[100000];

int cur = -1, R = -1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q;
	for (int i = 1; i <= N; i++) arr[i] = i;

	for (int i = 0; i < N; i++) {
		cin >> logs[i].first.first >> logs[i].first.second >> logs[i].second;
		logs[i].second = i + 1;
	}

	sort(logs, logs + N);

	for (int i = 0; i < N; i++) {
		if (R < logs[i].first.first) cur = logs[i].second, R = logs[i].first.second;
		else R = max(R, logs[i].first.second), arr[logs[i].second] = cur;
	}

	while (Q--) {
		int x, y; cin >> x >> y;
		cout << (findf(x) == findf(y)) << '\n';
	}
}