[백준/BOJ] 백준 15955번 : 부스터

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

15955번: 부스터

체크포인트(정점)간의 HP와 부스터를 효과적으로 사용하는 이동은 x축 또는 y축으로 HP를 사용하여 이동한 뒤, 부스터를 사용하는 것이라는 점을 이용한다. 

x좌표를 기준으로 정렬한 vector와, y좌표를 기준으로 정렬한 vector를 이용해서 x좌표 기준으로 거리가 가까운 점들 사이의 간선을 만들고 y좌표를 기준으로 거리가 가까운 점들 사이의 간선을 만들어서 간선들의 정보를 저장한다.

또한 쿼리는 오프라인 쿼리를 사용하기 위해 쿼리를 저장하여 HP순으로 정렬해 놓는다.

저장한 간선들을 최소 스패닝 트리를 만들어 가면서 쿼리의 HP가 작은것 순으로 해당 쿼리가 해당 간선을 이동할 수 있는지 여부를 체크했다. 해당 쿼리의 HP가 해당 간선의 가중치보다 작다면 해당 간선을 이동할 수 없으며 해당 간선보다 가중치가 큰 이후의 간선도 이동할 수 없다는 점을 이용하여 문제를 해결했다.

 

코드

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

int n, q;
vector<tuple<int, int, int>> x_y; //(x좌표, y좌표, 체크포인트)
vector<tuple<int, int, int>> y_x; //(y좌표, x좌표, 체크포인트)
vector<tuple<int, int, int>> edge; //(가중치, 체크포인트1, 체크포인트2)
vector<tuple<int, int, int, int>> query_info; //(가중치, 쿼리 번호, 체크포인트1, 체크포인트2) 
vector<int> parent(250001);
vector<int> rank_size(250001);
vector<pair<int, string>> result; //가중치 번호, 결과

void Pre()
{
	for (int i = 0; i < 250001; 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 = 1; i <= n; i++)
	{
		int x, y;
		cin >> x >> y;

		//정점간 HP와 부스터를 효과적으로 사용하는 이동은 x축 또는 y축으로 HP를 사용하여 이동한뒤, 부스터를 사용하는것

		x_y.push_back(make_tuple(x, y, i));
		y_x.push_back(make_tuple(y, x, i));
	}

	for (int i = 1; i <= q; i++)
	{
		int a, b, x;
		cin >> a >> b >> x;

		query_info.push_back(make_tuple(x, i, a, b)); //오프라인 쿼리 방법을 이용하기 위해 쿼리 저장
	}

	sort(x_y.begin(), x_y.end()); //x좌표 순으로 체크포인트 정렬
	sort(y_x.begin(), y_x.end()); //y좌표 순으로 체크포인트 정렬

	//x좌표 거리가 가까운 점들 사이의 간선을 만들고 저장
	for (int i = 1; i < x_y.size(); i++)
	{
		int cost = get<0>(x_y[i]) - get<0>(x_y[i - 1]);
		edge.push_back(make_tuple(cost, get<2>(x_y[i]), get<2>(x_y[i - 1])));
	}
	//y좌표 거리가 가까운 점들 사이의 간선을 만들고 저장
	for (int i = 1; i < y_x.size(); i++)
	{
		int cost = get<0>(y_x[i]) - get<0>(y_x[i - 1]);
		edge.push_back(make_tuple(cost, get<2>(y_x[i]), get<2>(y_x[i - 1])));
	}

	//간선의 가중치 순으로 정렬
	sort(edge.begin(), edge.end());

	//쿼리에서 가중치가 작은것 순으로 정렬
	sort(query_info.begin(), query_info.end());
	int query_check = 0;

	//간선을 이용해 최소 스패닝 트리를 만들어 간다
	for (int i = 0; i < edge.size(); i++)
	{
		if (query_check >= query_info.size()) //모든 쿼리를 다 확인 했을때
			break;

		int cost = get<0>(edge[i]);
		int u = get<1>(edge[i]);
		int v = get<2>(edge[i]);

		//확인해야 하는 쿼리의 HP가 해당 간선의 가중치보다 작을때
		//즉 확인하는 쿼리가 해당 간선을 이동할 수 없을때(해당 간선을 이동할 수 없으면 해당 간선 이후도 이동할 수 없다)
		//해당 간선이 연결되기 전에 쿼리를 확인해야 한다
		while (get<0>(query_info[query_check]) < cost)
		{
			//연결이 되어 있을때
			if (Find(get<2>(query_info[query_check])) == Find(get<3>(query_info[query_check])))
			{
				result.push_back(make_pair(get<1>(query_info[query_check]), "YES"));
			}

			//연결이 되어 있지 않을때
			else
			{
				result.push_back(make_pair(get<1>(query_info[query_check]), "NO"));
			}

			query_check++;

			if (query_check >= query_info.size())
				break;
		}

		if (Find(u) != Find(v))
			Merge(u, v);
	}

	//모든 쿼리 확인이 끝나지 않았을때
	while (query_check < query_info.size())
	{
		//연결이 되어 있을때
		if (Find(get<2>(query_info[query_check])) == Find(get<3>(query_info[query_check])))
		{
			result.push_back(make_pair(get<1>(query_info[query_check]), "YES"));
		}

		//연결이 되어 있지 않을때
		else
		{
			result.push_back(make_pair(get<1>(query_info[query_check]), "NO"));
		}

		query_check++;
	}

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

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

	return 0;
}