BOJ 31570 섬

문제 링크입니다.

문제 요약

삼각분할된 볼록 다각형이 주어집니다. 임의의 삼각형 안에 점 하나를 추가해 세 개의 삼각형으로 분할하는 행동을 원하는 만큼 할 수 있습니다. 이러한 행동의 수를 최소화하면서 두 개의 겹치지 않는 스패닝 트리를 만드세요.

해의 존재성

초기 상태에 그래프의 정점은 $N$개, 간선은 $2N-3$개이고 두 개의 스패닝 트리를 얻으려면 적어도 $2N-2$개의 간선이 필요하므로 최소한 한 번은 정점을 추가해야 합니다. 정점 하나를 추가하면 정점이 $N+1$개, 간선이 $2N$개이므로 모든 간선을 사용할 수 있다면 두 개의 스패닝 트리를 얻을 수 있습니다. 따라서 필요한 행동 수의 최솟값은 1입니다. 그러므로, 만약 항상 1번의 행동으로 겹치지 않는 두 개의 스패닝 트리를 얻어낼 수 있다면 그것이 하나의 최적해입니다.

구성 방법

그리디한 전략으로 이러한 해를 구성할 수 있어요.

• 초기 그래프에서 정점을 순서대로 순회하면서, 첫 번째 트리에 넣을 수 있는 간선을 다 넣고, 넣을 수 없는 간선은 두 번째 트리로 보냅니다. 이러한 알고리즘은 첫 번째 트리를 올바른 스패닝 트리로, 두 번째 트리를 0번 정점을 제외한 모든 정점을 잇는 스패닝 트리로 만듭니다.
• $0$번 정점과 $N-1$번 정점을 포함하는 유일한 삼각형을 분할합니다. 그 삼각형의 나머지 한 꼭짓점을 $i$번 정점이라 하면, 간선 $(N-1, N)$, $(N, 0)$을 두 번째 트리에, $(i, N)$을 첫 번째 트리에 추가합니다. 이제 두 트리가 모두 올바른 스패닝 트리가 됩니다.

전략의 첫 번째 단계가 올바르다면 두 번째 단계는 자명하게 올바릅니다. 첫 번째 단계의 정당성은 귀납적으로 증명할 수 있습니다.

$N=3$일 때는 자명합니다. 여기에 인접한 두 정점을 잇는 두 개의 간선을 그어 사이에 정점 하나를 반복적으로 추가하면 임의의 삼각분할 그래프를 만들어 낼 수 있습니다. $i$번 정점과 $j \gt i$번 정점 사이에 $k$번째 정점을 삽입했다고 치면, 간선 $(i, k)$는 반드시 첫 번째 트리에, $(j, k)$는 반드시 두 번째 트리에 삽입됨을 알 수 있습니다. 따라서 귀납적으로 두 트리가 각각 올바른 스패닝 트리와 $0$번 정점을 제외한 정점을 잇는 스패닝 트리임을 확인할 수 있습니다.

이를 ${\cal O}(N)$ 내지는 ${\cal O}(N \lg N)$ 정도에 구현하면 모든 서브태스크를 맞힐 수 있습니다.

코드

#include "island.h"
#include<bits/stdc++.h>
using namespace std;
 
vector<int> e[202020];
int par[202020], cnt[202020];
vector<array<int, 2>> tree1, tree2;
set<pair<int, int>> used;

int f(int x){
	return par[x] < 0 ? x : par[x] = f(par[x]);
}

void UNION(int x, int y){
	x = f(x); y = f(y);
	if(x == y) return;
	if(par[x] > par[y]) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

void construct_two_trees(int n, std::vector<int> U, std::vector<int> V){
	if(n == 3){
		add_vertex(0, 1, 2);
		tree1.push_back({0, 1});
		tree1.push_back({0, 2});
		tree1.push_back({2, 3});
		tree2.push_back({0, 3});
		tree2.push_back({1, 3});
		tree2.push_back({1, 2});
		report(tree1);
		report(tree2);
		return;
	}
	memset(par, -1, sizeof(par));
	for(int i = 0; i < n-1; i++){
		e[i].push_back(i+1);
	}
	e[0].push_back(n-1);
	int idx = 0;
	cnt[1] = cnt[n-2] = 1;
	for(int i = 0; i < U.size(); i++){
		e[U[i]].push_back(V[i]);
		e[V[i]].push_back(U[i]);
		if(U[i] == 0 || U[i] == n-1) cnt[V[i]]++;
		if(V[i] == 0 || V[i] == n-1) cnt[U[i]]++;
		if(cnt[U[i]] == 2) idx = U[i];
		if(cnt[V[i]] == 2) idx = V[i];
	}
	for(int i = 0; i < n; i++){
		for(auto nxt : e[i]){
			if(used.find({min(i, nxt), max(i, nxt)}) != used.end()) continue;
			used.insert({min(i, nxt), max(i, nxt)});
			if(f(i) == f(nxt)){
				tree2.push_back({i, nxt});
				continue;
			}
			tree1.push_back({i, nxt});
			UNION(i, nxt);
		}
	}
	add_vertex(0, idx, n-1);
	tree1.push_back({idx, n});
	tree2.push_back({0, n});
	tree2.push_back({n-1, n});
	report(tree1);
	report(tree2);
}