[알고리즘]Algospot_FORTRESS

출처 : https://algospot.com/judge/problem/read/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이라고 가정하며, 입력에 주어지는 성벽들은 서로 겹치거나 닿지 않습니다. 입력에 주어지는 첫 번째 성벽은 외벽이며, 외벽은 입력에 주어지는 모든 다른 성벽을 포함합니다.

출력

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

정답코드

#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

int t, 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 >> t;
	while (t--)
    {
		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;
}

풀이 및 사고과정

트리 구조로 데이터를 넣는 과정에 있어서 익숙하지 않다보니 어려웠다.
책을 참고해며 코드를 작성하면서 트리를 짜는 법을 조금 익힐 수 있었다.
그래도 계속보면서 익혀야겠다.