[Algospot] 요새 (문제 ID : FORTRESS)

문제

중세의 성과 요새들은 보안을 튼튼히 하면서도 더 넓은 영역을 보호하기 위해 여러 개의 성벽을 갖고 있었다고 하지요. 전세계에서 가장 편집증이 심한 영주가 지은 스트로고(Strawgoh) 요새는 이의 극치를 보여줍니다. 이 요새는 그림과 같이 커다란 원형 외벽 내에 여러 개의 원형 성벽이 겹겹이 지어진 형태로 구성되어 있는데, 어떤 성벽에도 문이 없어서 성벽을 지나가려면 사다리를 타고 성벽을 오르내려야 합니다. 요새 내에서도 한 곳에서 다른 곳으로 이동하는 데 시간이 너무 오래 걸린다는 원성이 자자해지자, 영주는 요새 내에서 왕래가 불편한 곳들을 연결하는 터널을 만들기로 했습니다. 계획을 세우기 위해 요새 내에서 서로 왕래하기 위해 가장 성벽을 많이 넘어야 하는 두 지점을 찾으려고 합니다. 예를 들어 위 그림의 경우, 별표로 표시된 두 지점 간을 이동하기 위해서는 다섯 번이나 성벽을 넘어야 하지요.

성벽들의 정보가 주어질 때 가장 성벽을 많이 넘어야 하는 두 지점 간을 이동하기 위해 몇 번이나 성벽을 넘어야 하는지 계산하는 프로그램을 작성하세요.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 100) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 성벽의 수 N (1 <= N <= 100) 이 주어집니다. 그 후 N 줄에는 각 3개의 정수로 각 성벽의 위치와 크기에 대한 정보 xi , yi , ri 가 주어집니다. (0 <= xi, yi <= 1000,1 <= ri <= 1000,0 <= i<N) 이 때 i 번 성벽은 (xi, yi) 를 중심으로 하는 반지름 ri 인 원형으로 설치되어 있습니다. 편의상 모든 성벽의 두께는 0이라고 가정하며, 입력에 주어지는 성벽들은 서로 겹치거나 닿지 않습니다. 입력에 주어지는 첫 번째 성벽은 외벽이며, 외벽은 입력에 주어지는 모든 다른 성벽을 포함합니다.

 

출력

각 테스트 케이스마다 한 줄에 두 지점 간 이동을 위해 최대 몇 번이나 성벽을 넘어야 하는지를 출력하세요.

---

구현할 게 많은 까다로운 문제다.

주어진 정보를 트리로 바꾸는 것과, 트리에서 최장 경로를 구하는 두 단계로 나뉜다.

 

첫번째 단계

트리는 getTree함수를 통해 생성하는데 0부터 N까지의 값중에 i 가 root의 자식이면 그 값을 루트로 다시 트리를 만들어 자식에 포함한다.

자식인지를 판별하는 법은, i가 root에 포함되는지를 먼저 파악한 후 포함이 된다면 다시 그게 바로 첫번째 자식인지를 판별한다. 

자식과 부모 사이에 다른 성이 있으면 안된다. 이를 판별하기위해 0부터 N을 모두 검사하며 사이에 다른 성이 있는지 확인한다.

없다면 자식에 포함하면된다.

 

두번째 단계

트리를 모두 구했으면 이제 최장 경로를 구하면 된다.

최장경로는 둘 중 하나로 나뉜다.

• 1. 가장 긴 루트-단말 노드 경로의 길이
• 2. 가장 긴 단말-단말 노드 경로의 길이

1번은 사실상 트리의 높이이다. 2번째 값만 구하면 된다. 

가장 긴 단말 - 단말 사이의 길이는 모든 단말 노드의 높이를 구해서 가장 긴 두 값을 더하면 된다. 코드를 보면 이해가 될 것이다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/FORTRESS.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int C, N, longest;
int x[101], y[101], r[101];
struct Tree {
	vector<Tree*> children;
};

int sqr(int x) {
	return x * x;
}

int sqrdist(int a, int b) {
	return (sqr(y[a] - y[b]) + sqr(x[a] - x[b]));
}

bool enclose(int a, int b) {
	return r[a] > r[b] && sqrdist(a, b) < sqr(r[a] - r[b]);
}

bool isChild(int parent, int child) {
	if (!enclose(parent, child))
		return false;
	for (int i = 0; i < N; i++) {
		if (i != parent && i != child && enclose(parent, i) && enclose(i, child))
			return false;
	}
	return true;
}

Tree* getTree(int root) {
	Tree* tmp = new Tree();
	for (int i = 0; i < N; i++) {
		if (isChild(root, i)) {
			tmp->children.push_back(getTree(i));
		}
	}
	return tmp;
}

int height(Tree* root) {
	vector<int> heights;
	for (int i = 0; i < root->children.size(); i++)
		heights.push_back(height(root->children[i]));
	if (heights.empty()) return 0;
	sort(heights.begin(), heights.end());
	if (heights.size() >= 2)
		longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights.size() - 1]);
	return heights.back() + 1;
}

int solve(Tree* root) {
	longest = 0;
	int h = height(root);
	return max(longest, h);
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> N;
		for (int i = 0; i < N; i++) 
			cin >> x[i] >> y[i] >> r[i];
		Tree* T = getTree(0);
		cout << solve(T) << endl;
	}
	return 0;
}