[백준/BOJ] 백준 5542번 : JOI 국가의 행사

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

5542번: JOI 국가의 행사

 

우선 축제로부터 각 정점까지 최단거리를 저장해 두고, 해당 값을 기반으로 각 간선들을 축제와 가장 먼 순으로 정렬을 한 뒤, 해당 순서로 간선을 그래프에 붙여 나가면서 유니온 파인드를 통해 같은 그룹의 정점은 묶어 나아간다. 같은 그룹으로 묶어 나아가다가 같은 그룹 내에 출발지와 도착점인 사람이 발견되면, 해당 사람의 축제로부터 가장 먼 길이는 방금 붙여지는 간선과 축제와의 거리라는 것을 통해 문제를 해결했다.

 

코드

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

int n, m, k, q;
vector<pair<int, int>> adj[100005];
vector<int> festival;
vector<int> short_dest(100005, 987654321); //축제 지역에서 거리

vector<tuple<int, int, int>> edge; //(축제와 가까운 거리, 정점1, 정점2);
set<int> node_check[100005]; //[정점번호] = 해당정점이 출발지 또는 도착지인 사람들

int parent[100005];
int rank_size[100005];

int result[100005];

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

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

void make_short_dest() {
	priority_queue<pair<int, int>> pq;

	for (int i = 0; i < festival.size(); i++) {
		pq.push(make_pair(-0, festival[i]));
		short_dest[festival[i]] = 0;
	}

	while (!pq.empty()) {
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		if (here_cost > short_dest[here]) {
			continue;
		}

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (there_cost < short_dest[there]) {
				short_dest[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}
		}
	}
}

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

	pre();

	cin >> n >> m >> k >> q;

	vector<pair<int, int>> temp_edge;
	for (int i = 0; i < m; i++) {
		int u, v, cost;
		cin >> u >> v >> cost;

		adj[u].push_back(make_pair(cost, v));
		adj[v].push_back(make_pair(cost, u));

		temp_edge.push_back(make_pair(u, v));
	}

	for (int i = 0; i < k; i++) {
		int number;
		cin >> number;
		festival.push_back(number);
	}
	make_short_dest();

	//각 간선에서 축제까지 거리를 기준으로 정렬을 한다
	for (int i = 0; i < m; i++) {
		int u = temp_edge[i].first;
		int v = temp_edge[i].second;
		int festival_dist = min(short_dest[u], short_dest[v]); //해당 간선과 가장 가까운 축제와 거리

		edge.push_back(make_tuple(festival_dist, u, v));
	}

	//간선을 축제와의 거리 내림차순 정렬
	sort(edge.begin(), edge.end());
	reverse(edge.begin(), edge.end());

	//출발지, 도착지가 되는 정점에 사람 정보 저장
	for (int i = 0; i < q; i++) {
		int start, dest;
		cin >> start >> dest;

		node_check[start].insert(i);
		node_check[dest].insert(i);
	}

	//축제와의 거리가 먼 간선 순으로 연결해 나가면서 축제를 싫어하는 사람이 출발지에서 도착지까지 가게 되는지 유니온 파인드를 통해 확인
	for (int i = 0; i < edge.size(); i++) {
		int festival_dist = get<0>(edge[i]);
		int u = get<1>(edge[i]);
		int v = get<2>(edge[i]);

		u = find(u);
		v = find(v);

		if (u == v) {
			continue;
		}

		int big_node, small_node; //유니온에서 small_node쪽에서 big_node쪽으로 합쳐진다
		if (rank_size[u] < rank_size[v]) {
			big_node = v;
			small_node = u;
		}
		else {
			big_node = u;
			small_node = v;
		}

		//정점 small_node 그룹이 출발지(도착지)이고, 정점 big_node 그룹이 도착지(출발지)인 사람이 있는지 확인
		for (set<int>::iterator it = node_check[small_node].begin(); it != node_check[small_node].end(); it++) {
			int human = (*it);

			if (node_check[big_node].count(human) != 0) { //해당 사람이 가는 길이 연결 될때
				result[human] = festival_dist;
			}

			node_check[big_node].insert(human); //big_node쪽으로 합쳐진다
		}

		merge(u, v);
	}

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

	return 0;
}