🚀 [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이라고 가정하며, 입력에 주어지는 성벽들은 서로 겹치거나 닿지 않습니다. 입력에 주어지는 첫 번째 성벽은 외벽이며, 외벽은 입력에 주어지는 모든 다른 성벽을 포함합니다.
🖥 출력
각 테스트 케이스마다 한 줄에 두 지점 간 이동을 위해 최대 몇 번이나 성벽을 넘어야 하는지를 출력하세요.
🖱 입력 예제
2
3
5 5 15
5 5 10
5 5 5
8
21 15 20
15 15 10
13 12 5
12 12 3
19 19 2
30 24 5
32 10 7
32 9 4
💻 출력 예제
2
5
💎 전체 코드는 다음과 같습니다.
//
// FORTRESS.cpp
// AALGGO
//
// Created by inhyeok on 2021/12/06.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("FORTRESS.txt");
struct TreeNode{
vector<TreeNode*> children;
};
int n, y[100], x[100], radius[100];
int sqr(int x){
return x*x;
}
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){
int dist = sqrdist(a,b);
return ((radius[a] > radius[b])&&(dist<sqr(radius[a]-radius[b])));
}
// parent 가 child를 포함하는지 확인한다.
bool isChild(int parent, int child){
if(!encloses(parent,child)) return false;
for(int i=0; i<n; i++){
if(i!=parent && i!=child && encloses(parent,i) && encloses(i,child))
return false;
}
return true;
}
TreeNode* getTree(int root){
TreeNode* ret = new TreeNode();
for(int ch=0; ch<n; ch++){
if(isChild(root, ch)) ret->children.push_back(getTree(ch));
}
return ret;
}
int longest;
int height(TreeNode* 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());
// root를 최상위 노드로하는 경로를 고려함.
// 자식의 서브트리의 높이를 오름차순으로 heights를 정렬 했기 때문에
// heights.size()-2 => 두번째로 높음
// heights.size()-1 => 가장 높음
// 두가지를 더해줘 가장 긴 leaf 와 leaf 의 거리를 구한다.
// +2 => 두 자식노드에서 root로 하나씩 가는것을 더해줘야하기때문.
if(heights.size() >=2)
longest = max(longest, 2+heights[heights.size()-2]+heights[heights.size()-1]);
// 트리 높이는 루트를 서브트리의 높이의 최대치에 1을 더해 계산함.
return heights.back()+1;
}
int solve(TreeNode* root){
longest = 0;
int h = height(root);
return max(longest, h);
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
fin >> n;
for(int i=0; i<n; i++){
fin >> x[i] >> y[i] >> radius[i];
}
TreeNode* Tree = getTree(0);
cout << solve(Tree)<< endl;
}
}
Comments