취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10379번 문제인 Hiking in the Hills이다.
문제는 아래 링크를 확인하자.

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

어떤 정수점 경로가 있을 때, 해당 경로가 지나는 점을 각 점이 존재하는 삼각형 면 위에서 적절하게 옮겨 경로의 최고점을 증가시키지 않고 삼각형의 꼭짓점으로 이동시킬 수 있다. 따라서, 시작점과 끝점을 제외한 모든 점이 주어진 꼭짓점들로만 구성된 경로가 존재한다.

따라서, 시작점과 끝점을 그 점이 포함된 삼각형의 꼭짓점들로 한 번 연결하고, 주어진 꼭짓점들을 높이가 낮은 순으로 정렬하고, 각 점을 하나씩 추가하면서 MST를 구성하듯이 최적 높이의 경로를 찾아 문제를 해결하자.

시작점과 끝점이 원래의 꼭짓점 또는 변의 위에 있는 경우 예외처리가 필요함에 유의하자.

아래는 제출한 소스코드이다.

//MST 응용구현
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int uf[3000];
int findf(int cur) {
	if (cur == uf[cur]) return cur;
	return uf[cur] = findf(uf[cur]);
}

ll AREA(pair<int, int> &p1, pair<int, int> &p2, pair<int, int> &p3) {
	return abs((ll)p1.first * p2.second + (ll)p2.first * p3.second + (ll)p3.first * p1.second - (ll)p1.first * p3.second - (ll)p2.first * p1.second - (ll)p3.first * p2.second);
}

int N, mS, mE, X, Y, Z;
int H[3000];
int midx;
map<pair<int, int>, int> mp;
pair<int, int> invmp[3000];
vector<pair<int, pair<int, int>>> E;
vector<pair<int, pair<int, int>>> T;

vector<int> G[3000];
int gparent[3000];
void dfs(int cur, int par) {
	gparent[cur] = par;
	for (auto &nxt:G[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur);
	}
}
vector<int> ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3; cin >> X1 >> Y1 >> Z1 >> X2 >> Y2 >> Z2 >> X3 >> Y3 >> Z3;
		int idx1, idx2, idx3;
		if (!mp.count(make_pair(X1, Y1))) {
			mp[make_pair(X1, Y1)] = midx;
			invmp[midx] = make_pair(X1, Y1);
			H[midx] = Z1;
			midx++;
		}
		idx1 = mp[make_pair(X1, Y1)];
		if (!mp.count(make_pair(X2, Y2))) {
			mp[make_pair(X2, Y2)] = midx;
			invmp[midx] = make_pair(X2, Y2);
			H[midx] = Z2;
			midx++;
		}
		idx2 = mp[make_pair(X2, Y2)];
		if (!mp.count(make_pair(X3, Y3))) {
			mp[make_pair(X3, Y3)] = midx;
			invmp[midx] = make_pair(X3, Y3);
			H[midx] = Z3;
			midx++;
		}
		idx3 = mp[make_pair(X3, Y3)];
		E.emplace_back(make_pair(max(Z1, Z2), make_pair(idx1, idx2)));
		E.emplace_back(make_pair(max(Z2, Z3), make_pair(idx2, idx3)));
		E.emplace_back(make_pair(max(Z3, Z1), make_pair(idx3, idx1)));
		T.emplace_back(make_pair(idx1, make_pair(idx2, idx3)));
	}
	
	cin >> X >> Y >> Z;
	if (mp.count(make_pair(X, Y))) mS = mp[make_pair(X, Y)];
	else {
		auto S = make_pair(X, Y);
		mS = mp[S] = midx;
		invmp[midx] = S;
		H[midx] = Z;
		for (auto p:T) {
			int idx1 = p.first, idx2 = p.second.first, idx3 = p.second.second;
			auto p1 = invmp[idx1], p2 = invmp[idx2], p3 = invmp[idx3];
			ll A = AREA(p1, p2, p3);
			ll A1 = AREA(p1, p2, S), A2 = AREA(p2, p3, S), A3 = AREA(p3, p1, S);
			if (A == A1 + A2 + A3) {
				E.emplace_back(make_pair(H[idx1], make_pair(idx1, midx)));
				E.emplace_back(make_pair(H[idx2], make_pair(idx2, midx)));
				E.emplace_back(make_pair(H[idx3], make_pair(idx3, midx)));
			}
		}
		midx++;
	}
	cin >> X >> Y >> Z;
	if (mp.count(make_pair(X, Y))) mE = mp[make_pair(X, Y)];
	else {
		auto S = make_pair(X, Y);
		mE = mp[S] = midx;
		invmp[midx] = S;
		H[midx] = Z;
		for (auto p:T) {
			int idx1 = p.first, idx2 = p.second.first, idx3 = p.second.second;
			auto p1 = invmp[idx1], p2 = invmp[idx2], p3 = invmp[idx3];
			ll A = AREA(p1, p2, p3);
			ll A1 = AREA(p1, p2, S), A2 = AREA(p2, p3, S), A3 = AREA(p3, p1, S);
			if (A == A1 + A2 + A3) {
				E.emplace_back(make_pair(H[idx1], make_pair(idx1, midx)));
				E.emplace_back(make_pair(H[idx2], make_pair(idx2, midx)));
				E.emplace_back(make_pair(H[idx3], make_pair(idx3, midx)));
			}
		}
		midx++;
	}
	for (int i = 0; i < midx; i++) uf[i] = i;
	sort(E.begin(), E.end());
	for (auto &p:E) {
		if (findf(mS) == findf(mE)) break;
		int x = p.second.first, y = p.second.second;
		int xx = findf(x), yy = findf(y);
		if (xx != yy) {
			uf[yy] = xx;
			G[x].emplace_back(y);
			G[y].emplace_back(x);
		}
	}
	dfs(mS, mS);
	while (mE != mS) {
		ans.emplace_back(mE);
		mE = gparent[mE];
	}
	ans.emplace_back(mS);
	cout << ans.size() << '\n';
	reverse(ans.begin(), ans.end());
	for (auto &idx:ans) {
		cout << invmp[idx].first << ' ' << invmp[idx].second << ' ' << H[idx] << '\n';;
	}
}