백준 1626: 두 번째로 작은 스패닝 트리

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

 

지금까지 다이아 5가 푼 문제 중 최고 난이도였던 내가, 다이아 4인 이 문제를 도전하게 된 것은 의외의 계기가 있었다.

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

이 문제를 해결하기 위해서, 아이디어를 하나 떠올렸는데, 마침 이 문제에 적용할 수 있을 것 같아서 도전을 하게 되었다. 

 

당시 아이디어는 이러하다.

각 간선 하나를 미리 Union해서 MST 알고리즘을 돌리면 문제를 해결할 수 있을 것 같은데, 그러면 십중팔구 시간초과가 발생할 것이다. 그렇다면, 어떻게 해결해야할까?

각 간선의 길이와 번호는 동일하다고 하자. 이 문제의 MST는 1, 2, 3번 간선을 이으면 된다.

그런데, 4번 간선을 연결한 MST는 어떨까?

3번 간선을 제외하면 된다.  이런 방식으로 여러 그래프를 머릿속으로 그려본 결과, MST에 포함 안 된 특정 간선 하나를 포함한 MST는 기존의 MST에 간선 하나만 건들이면 정답이란 결론을 내렸다.

 

그러자, 이전에 마주했던 백준 1626: 두 번째로 작은 스패닝 트리가 머리를 스쳤다. 혹시, 이 아이디어를 여기에 적용할 수 없을까?란 생각이 들었다. 이 문제보다 간단하게, 기존에 사용하지 않은 간선 중 가장 작은 간선을 포함한 MST를 사용하면 정답일 것이다!란 생각으로 이 문제에 도전했다. 

 

그런데 문제가 하나 있었다. 기존의 MST 간선 중 어떤 간선을 건들여야할 지가 문제였다. 나는 단순하게 LCA로 구한 정점으로 구성된 간선을 사용하면 되지 않을까? 란 생각과 함께 시도하였는데, 결과적으로 실패했다.

문제점은 두 가지가 있었다.

 

1. MST 간선 중 어떤 간선을 건들여야할지가 틀렸다.

2. MST에 포함 안 된 간선 중, 어떤 간선을 포함되어야할지가 틀렸다.

 

1번은 그렇다쳐도 2번이 다소 의외였는데, 이 아이디어로 이 문제에 도전한거라서, 머릿속이 복잡해졌다. 다소 머리를 식히고, 천천히 생각을 하였고, 2번의 경우, MST에 포함 안 된 모든 간선을 시험해보자는 결론을 내렸다.

문제는 1번이였다. MST로 만든 그래프를 활용해서, LCA를 구한다음 그 과정에서, 지나친 가장 큰 간선과 현재의 간선을 비교한다는 아이디어는 떠올렸는데, 문제는, 이것을 어떻게 구현할 것이냐였다. 단순 DFS는 시간초과가 날 것을 불보듯 뻔한데, 어떻게 해야할까? 희소배열을 활용할까? 그렇기엔, 내 희소배열에 대한 지식이 부족했다.

 

많은 생각 끝에 결국 구글링을 거쳤는데, 아니나다를까, 희소배열을 활용하는 게 맞았다. pair로 가장 큰 길이와 그 다음 길이를 저장한 뒤, LCA를 구할때, 비교하면 된다. 이렇게 말을 하면 간단하지만, 구현이 생각 이상으로 까다로웠다. 그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cstring>

using namespace std;
using pii = pair<int, int>;
const int MAX = 50001;
const int INF = 1000000007;
unordered_map<int, int> adj[MAX];
vector<pair<int, pii>> edges;
int V, E, depth[MAX], A, B, C, dp[MAX][22], P[MAX], ans[MAX], cnt = 0, S = 0, p = INF;
pii L[MAX][22];
bool sel[MAX];
void dfs(int here, int parent)
{		
	for (const pair<int, int> p : adj[here])
		if (p.first != parent)
		{
			depth[p.first] = depth[here] + 1;
			dp[p.first][0] = here;
			L[p.first][0] = pii(p.second, -1);
			dfs(p.first, here);
		}
}
int find(int u)
{
	if (P[u] == u) return u;
	return P[u] = find(P[u]);
}
void merge(int u, int v)
{
	u = find(u);
	v = find(v);
	if (u > v) swap(u, v);
	P[v] = u;
}

int solve(pair<int, pii>& ee)
{
	int a = ee.second.first;
	int b = ee.second.second;
	int w = ee.first;
	int ret = -1;
	if (depth[a] < depth[b]) swap(a, b);
	int diff = depth[a] - depth[b];
	int cnt = 0;
	while (diff)
	{
		if (diff % 2 == 1)
		{
			if (L[a][cnt].first != w)
				ret = max(ret, L[a][cnt].first);
			else if (L[a][cnt].second != -1)
				ret = max(ret, L[a][cnt].second);
			a = dp[a][cnt];
			depth[a];
		}
		diff /= 2;
		++cnt;
	}
	if (a != b) {
		for (int i = 20; i >= 0; i--) {
			if (dp[a][i] != dp[b][i]) {
				if (L[a][i].first != w)
					ret = max(ret, L[a][i].first);
				else if (L[a][i].second != -1)
					ret = max(ret, L[a][i].second);
				if (L[b][i].first != w)
					ret = max(ret, L[b][i].first);
				else if (L[b][i].second != -1)
					ret = max(ret, L[b][i].second);
				a = dp[a][i];
				b = dp[b][i];
			}
		}
		if (L[a][0].first != w)
			ret = max(ret, L[a][0].first);
		else if (L[a][0].second != -1)
			ret = max(ret, L[a][0].second);
		if (L[b][0].first != w)
			ret = max(ret, L[b][0].first);
		else if (L[b][0].second != -1)
			ret = max(ret, L[b][0].second);

		a = dp[a][0];
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> V >> E;
	for (int i = 0; i <= V; i++) P[i] = i;
	for (int i = 0; i < E; i++)
	{
		cin >> A >> B >> C;
		edges.push_back({ C, {A, B} });
	}
	std::sort(edges.begin(), edges.end());
	for (int i = 0; i < edges.size(); i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (find(a) != find(b))
		{
			merge(a, b);
			adj[a][b] = cost;
			adj[b][a] = cost;
			S += cost;
			++cnt;
			sel[i] = true;
		}
	}
	depth[0] = depth[1] = -1;
	dfs(1, 0);
	if (cnt != V - 1)
	{
		cout << -1 << '\n';
	}
	else
	{
		for (int j = 0; j <= 20; j++) {
			for (int i = 1; i <= V; i++) {
				if (dp[i][j] >= 0 && dp[dp[i][j]][j] >= 0) {
					pii b = L[i][j]; pii a = L[dp[i][j]][j];
					vector<int> tmp = { b.first, b.second, a.first, a.second };
					int f = -1, s = -1;
					for (int n : tmp) f = max(f, n);
					for (int n : tmp)
						if (n != f)
							s = max(s, n);
					L[i][j + 1] = { f, s };
					dp[i][j + 1] = dp[dp[i][j]][j];
				}
			}
		}
		for (int i = 0; i < edges.size(); i++)
		{
			if (sel[i]) continue;
			int t = solve(edges[i]);
			if (t == -1 || edges[i].first == t) continue;
			p = min(p, edges[i].first - t);
		}
		if (p == INF) cout << -1 << '\n';
		else cout << S + p << '\n';
	}
}

 

희소배열은 사용할 일이 많이 없어서, 오랜만에 사용하게 되었는데, 정말이지 언제 봐도 까다롭다. 더욱이 이렇게 활용하는 것은 이번이 처음이다. 그러다보니 많이 헤매었던 것 같다.

다른 분들이 구현하신 코드를 참조했는데, 기존의 내 코드와 합치고, 디버깅하는 과정이 정말로 힘들었던 것 같다.

 

참조: https://mapocodingpark.blogspot.com/2020/02/BOJ-1626.html

백준 1626번 두 번째로 작은 스패닝 트리