[알고스팟] - 요새

문제 : 요새 (난이도 : 中)

 

https://algospot.com/judge/problem/read/FORTRESS

 

 분석

 주어진 데이터를 트리 형태로 가공하면 쉽게 답을 구할 수 있다. 트리 형태에서 최장 길이는 다음 중 긴 길이에 해당된다.

 

1. 트리의 높이

2. 잎-잎 길이

 

입력 데이터 중 첫 번째 데이터는 성 외곽이므로 트리의 root로 설정하고, 나머지 tree를 구성하면 된다.

 

 구현

struct TreeNode
{
	vector<TreeNode*> children;
};

// leaf to leaf len
int longest;
// root를 루트로하는 subtree의 높이를 반환.
int height(TreeNode* root)
{
	vector<int> heights;
	for (size_t 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(TreeNode* root)
{
	longest = 0;
	// 트리의 높이와 최대 잎-잎 경로 중 큰 것을 선택
	int h = height(root);
	return max(longest, h);
}


// input datas 가공
int n, y[100], x[100], rad[100];
int sqr(int x)
{
	return x * x;
}
// 두 성벽 a, b 중심점 간의 거리의 제곱을 반환
int sqrdist(int a, int b)
{
	return sqr(y[a] - y[b]) + sqr(x[a] - x[b]);
}
// 성벽 a 가 성벽 b를 포함하는지 반환
bool encloses(int a, int b)
{
	return rad[a] > rad[b] && sqrdist(a, b) < sqr(rad[a] - rad[b]);
}
// 성벽 트리에서 parent가 child의 부모인지 확인
bool isChild(int parent, int child)
{
	if (!encloses(parent, child)) return false;
	for (size_t i = 0; i < n; i++)
	{
		if (i != parent && i != child &&
			encloses(parent, i) && encloses(i, child)) return false;
	}
	return true;
}
// root 성벽을 루트로 하는 트리를 생성
TreeNode* getTree(int root)
{
	TreeNode* ret = new TreeNode();
	for (int ch = 0; ch < n; ch++)
	{
		// ch 성벽이 root 성벽에 직접적으로 포함되어 있다면
		// 트리를 만들고 자손 목록에 추가
		if (isChild(root, ch))
		{
			ret->children.push_back(getTree(ch));
		}
	}
	return ret;
}

int main()
{
	int c;
	cin >> c;

	while (c--)
	{
		cin >> n;
		for (size_t i = 0; i < n; i++)
		{
			cin >> x[i] >> y[i] >> rad[i];
		}
		TreeNode* root = getTree(0);
		cout << solve(root) << '\n';
	}
	return 0;
}

 

height() 함수를 해석하는 데 오래 걸렸다...