[BOJ] 1396 크루스칼의 공

문제 링크: https://www.acmicpc.net/problem/1396

문제 요약

간선에 가중치가 존재하는 그래프가 존재하는데, 다음과 같은 쿼리를 빠르게 처리해야 한다.

• 정점 x에서 시작해서 y까지 이동하려고 할 때, 이용해야 하는 간선의 최소 가중치는 얼마인가? 그리고 x에서부터 그 가중치로 방문할 수 있는 정점의 개수는 몇 개인가?

문제 풀이

두 가지 풀이가 존재한다.

(1) 병렬 이분 탐색

한 쿼리에 대해서 다음과 같은 문제를 해결한다고 생각해보자.

• 정점 x에서 시작해서 k 이하의 가중치를 갖는 간선만을 사용할 수 있을 때, 정점 y에 방문할 수 있는가? 또한 이 때 정점 x로부터 방문할 수 있는 정점의 개수는 얼마인가?

이 문제를 해결하는 방법은 쉽다. 말 그대로 k 이하의 가중치를 가지는 간선만을 가지고 BFS를 수행하면 된다. 하지만 쿼리가 여럿일 때는 쉽게 활용될 수 있는 방법이 아니니, 조금 비효율적이더라도 확장성이 더 높은 방법으로 문제를 해결해 보자. 크루스칼 알고리즘을 이용해서 간선의 가중치가 작은 순서대로 정점들을 union시키고, x와 y가 합쳐졌을 때 그 컴포넌트의 크기와 활용한 간선의 가중치가 정답이 된다. 이 문제를 해결할 수 있다면 원래 쿼리도 파라메트릭 서치를 해 줌으로서 정렬에 $O(ElogE)$, 쿼리당 $O( E \log V \log E$)$에 수행이 가능하다. 물론 당장은 크루스칼 알고리즘을 Naive하게 활용해도 이것보다는 빠르게 할 수 있다.

하지만 굳이 이러한 방식으로 돌아서 쿼리를 수행해야 하는 이유가 있다. 위 과정 각 쿼리에 대해서 한 번씩 전부 수행하면 당연히 매우 느리나, 쿼리를 모두 동시에 보고 오프라인으로 수행하면 이분 탐색의 한 과정을 같이 진행해줄 수 있다. 크루스칼 알고리즘은 BFS와 달리 시작 정점에 구애받지 않기 때문에 모든 쿼리에 대해 연결성을 판별해줄 수 있고, Naive하게 수행하지 않고 파라메트릭 서치와 같은 형태를 사용하면 각 쿼리에 대해 '가능해지는 순간'을 하나의 간선을 추가할 때 마다 모든 쿼리를 보지 않고도 빠르게 구해줄 수 있다. 

구체적인 과정은 다음과 같다. 어떤 쿼리를 위에서 기술한 결정 문제로 해결한다면, 답의 범위가 1에서부터 E까지(어차피 정답은 간선들의 가중치 중 하나이므로, 가중치 대신 정렬된 간선의 번호를 사용해도 무방하다)로 나타날 것이고 이 위에서 이분 탐색을 진행할 것이다. 이 때 모든 쿼리에 대해 이분 탐색을 할 지점, 즉 답을 업데이트 해야 하는 시점을 계산해 두고 관리한다. 그 다음 크루스칼 알고리즘을 한 번 수행하면서 union을 한 번 할 때 마다 이 시점에 답을 업데이트 해야 하는 모든 쿼리에 대해 이동 가능 여부와 컴포넌트 크기를 갱신해준다. 이 모든 과정이 $(\log E)$번 이루어지고, 각 과정마다 $O(Q+E \log V)$만큼이 걸리니 총 시간복잡도는 처음에 수행해주는 정렬까지 해서 $ O(E \log E + (Q+E \log V) \log E) $ = $ O(Q \log E + E \log E) $ 이다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef tuple<int, int, int> edge;

struct UF{
	int n; vector<int> par, sz;
	UF(int _n) : n(_n), par(_n + 1), sz(_n+1,1) {
		for (int i = 1; i <= n; i++)
			par[i] = i;
	}
	int fi(int x) {
		if (x == par[x]) return x;
		else return par[x] = fi(par[x]);
	}
	void un(int a, int b) {
		a = fi(a); b = fi(b);
		if (a == b) return;
		par[a] = b;
		sz[b] += sz[a];
	}
};

struct query {
	int x, y, le, ri, mv, rt;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, q;
	cin >> n >> m;

	vector<edge> e;
	for (int i = 0; i < m; i++) {
		int t1, t2, t3;
		cin >> t1 >> t2 >> t3;
		e.emplace_back(t3, t1, t2);
	}
	sort(e.begin(), e.end());

	cin >> q;
	vector<query> qr;
	for (int i = 0; i < q; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		qr.push_back({ t1,t2,1,m,0,-1});
	}

	while (true) {
		vector<vector<int>> G(m + 1);
		bool chk = false;
		for (int i = 0; i < q; i++) {
			query &hr = qr[i];
			if (hr.le <= hr.ri) {
				chk = true;
				G[(hr.le + hr.ri) / 2].push_back(i);
			}
		}
		if (!chk) break;

		UF un(n+1);
		for (int i = 0; i < m; i++) {
			int v, x, y; tie(v, x, y) = e[i];
			if (un.fi(x) != un.fi(y)) un.un(x, y);
			for (int ht : G[i + 1]) {
				query &hq = qr[ht];
				if (un.fi(hq.x) == un.fi(hq.y)) {
					hq.ri = i;
					hq.mv = un.sz[un.fi(x)];
					hq.rt = v;
				}
				else
					hq.le = i + 2;
			}
		}
	}
	for (int i = 0; i < q; i++) {
		if (qr[i].rt == -1) cout << -1 << '\n';
		else cout << qr[i].rt << ' ' << qr[i].mv << '\n';
	}
		
	return 0;
}

 

(2) LCA

이건 크레이피쉬 글쓰는 기계나 시간여행자의 실험기록같은 문제에서 보고 대체 이걸 어디에다 써... 하던 기법인데 여기다 쓴다는 것을 들었다. 크루스칼 알고리즘에서 정점 쌍들이 각각 언제 union되는지, 그리고 어떤 순서로 union 되었는지를 트리 구조로 관리해 보자. 컴포넌트 2개가 union되면, 기존에 컴포넌트를 나타내는 정점 2개를 자식 노드로 하고 두 컴포넌트를 합친 컴포넌트를 나타내는 정점을 새로 만든다. 또 이 정점에 현재 이 컴포넌트의 사이즈와, 지금까지 몇 번의 union 시도가 있었는지를 기록한다. 그러면  임의의 두 정점이 합쳐지는 가장 빠른 시간은 처음에 그 두 단일 정점을 나타내는 컴포넌트에 해당하는 트리 정점 2개가 합쳐질 때의 시간, 즉 두 트리 정점의 LCA일 것이다. LCA는 전처리를 통해서 빠르게 구해줄 수 있다. 이렇게 알고리즘 수행이 비가역적인 상황에서 시간축을 트리 형태로 만들어서 관리해야 하는 문제가 꽤 나온다고 알고 있다.

풀이의 시간복잡도는 한번 크루스칼 알고리즘을 실행하는 $O(E \log E + E \log V)$에 전처리 $O(V \log V)$, 쿼리당 LCA를 한번 구하므로 $O(Q \log V)$를 합쳐서 총 $O(E \log V+ E \log E + V \log V + Q \log V)$ = $O(E \log E + Q \log V)$ 이다. 더럽다

코드

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> edge;

struct node {
	int p, sz, tm;
};

int top = 1;
node nd[200005];
int par[200005][20];
vector<int> child[200005];
int depth[200005], inter[200005];

struct UnionFind {
	vector<int> par, sz, idx;
	UnionFind(int _n) : par(_n + 1), sz(_n + 1, 1), idx(_n + 1) {
		for (int i = 1; i <= _n; i++) par[i] = idx[i] = i;
	}
	int fi(int x) {
		if (par[x] == x) return x;
		else return par[x] = fi(par[x]);
	}
	void un(int a, int b, int tm) {
		a = fi(a); b = fi(b);
		if (a == b) return;
		nd[idx[a]].p = top;
		nd[idx[b]].p = top;
		par[a] = b;
		sz[b] += sz[a];
		inter[idx[a]] = inter[idx[b]] = 1;
		nd[top] = { top,sz[b],tm };
		child[top].push_back(idx[a]);
		child[top].push_back(idx[b]);

		idx[b] = top;
		top++;
	}
};

int n, m;

void dfs(int x, int dp) {
	depth[x] = dp;
	for (int th : child[x])
		dfs(th, dp + 1);
}

void process() {
	for (int i = 1; i < top; i++)
		if (!inter[i]) dfs(i, 1);
	for (int i = 1; i < top; i++)
		par[i][0] = nd[i].p;
	for (int i = 1; i <= 19; i++)
		for (int j = 1; j < top; j++)
			par[j][i] = par[par[j][i - 1]][i - 1];
}

int lca(int a, int b){	
	if (depth[a] > depth[b]) swap(a, b);
	int sub = depth[b] - depth[a];
	int k = 0;
	while (sub) {
		if (sub & 1) b = par[b][k];
		sub = sub >> 1; k++;
	}
	if (a == b) return a;
	for (int i = 19; i >= 0; i--) {
		if (par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	vector<edge> e;
	for (int i = 0; i < m; i++) {
		int t1, t2, t3;
		cin >> t1 >> t2 >> t3;
		e.emplace_back(t3, t1, t2);
	}
	sort(e.begin(), e.end());
	
	for (int i = 1; i <= n; i++) {
		nd[top++] = { i,1,-1 };
	}

	UnionFind uf(n + 1);
	for (int i = 0; i < e.size(); i++) {
		int v, st, en;
		tie(v, st, en) = e[i];
		uf.un(st, en, i);
	}
	process();
	int q; cin >> q;
	while (q--) {
		int x, y; cin >> x >> y;
		if (uf.fi(x) != uf.fi(y)) {
			cout << "-1\n";
			continue;
		}
		int l = lca(x, y);
		cout << get<0>(e[nd[l].tm]) << ' ' << nd[l].sz << '\n';
	}
	return 0;
}

마무리

사실 이거, 나중에 설명할 Particle Swapping이랑 똑같은 문제다. 병렬 이분 탐색은 속도가 구리니까 코딩이 힘들더라도 그냥 LCA 접근을 사용하는 게 더 편하다.