[백준/BOJ] 백준 17619번 : 개구리 점프

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

17619번: 개구리 점프

 

유니온 파인드를 통해 겹치는 구간은 유니온을 통해 하나로 묶어서, 각 쿼리에 대해 두 통나무가 같은 그룹인지 확인하는 방법으로 문제를 해결했다.

 

코드

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

int n, q;
vector<pair<pair<int, int>, int>> range; //((범위),통나무 번호)
int parent[100005];
int rank_size[100005];

void pre() {
	for (int i = 0; i < 100005; i++) {
		parent[i] = i;
		rank_size[i] = 1;
	}
}

int find(int u) {
	if (parent[u] == 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_size[u] < rank_size[v]) {
		parent[u] = v;
	}

	else {
		parent[v] = u;

		if (rank_size[u] == rank_size[v]) {
			rank_size[u]++;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	pre();

	cin >> n >> q;

	for (int i = 0; i < n; i++) {
		int left, right, y;
		cin >> left >> right >> y;
		range.push_back(make_pair(make_pair(left, right), i + 1));
	}

	sort(range.begin(), range.end());

	for (int i = 1; i < range.size(); i++) {

		pair<int, int> before_range = range[i - 1].first;
		pair<int, int> here_range = range[i].first;

		//두 범위가 겹치는지 확인
		if (before_range.second >= here_range.first) {
			//겹치면 유니온
			merge(range[i - 1].second, range[i].second);

			//겹치면 현재 범위의 오른쪽 끝을 before_range와 here_range 중 큰거로 바꿔준다 (이제 같은 그룹이므로, 뒤에 있을 range[i+1]랑 비교를 위해)
			range[i].first.second = max(before_range.second, here_range.second);
		}
	}

	vector<int> result;
	for (int i = 0; i < q; i++) {
		int u, v;
		cin >> u >> v;

		if (find(u) == find(v)) {
			result.push_back(1);
		}

		else {
			result.push_back(0);
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}