[Algospot] 알고스팟 FORTRESS 요새

출처: https://www.algospot.com/judge/problem/read/FORTRESS

 Input 

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

 

 Output 

2

5

 

성벽들이 서로 닿거나 겹치지 않는다는 조건에서 계층적 구조를 알 수 있습니다.

(두 원은 서로 떨어져 있거나 하나의 원이 다른 하나의 원안에 있습니다.)

▶ 성벽들간의 간의 포함 관계를 트리로 표현 가능

 

① 트리 생성

0번 성벽은 다른 모든 성벽을 포함하는 외벽이므로, 트리의 루트로 정의

0번 성벽 바로 밑에 들어갈 성벽들을 찾고, 각각의 성벽을 루트로 하는 서브트리를 재귀적으로 생성

원(성벽)들을 모두 비교하면서 자신의 직계 부모를 찾습니다.

i 번째 원이 root에 포함되는지 확인한 후 포함이 되는 경우 다시 첫번째 자식인지를 판별

▶ 부모와 자식상에 다른 원이 존재여부로 판별

ex) B가 A에 포함될 때, 또 다른 성벽 i가 A에 포함되면 B를 포함하는지 확인

 

두 원의 포함여부는 아래와 같이 확인

 

② 생성된 트리에서 최장 경로 구하기

트리 내에서 최장 경로는 크게 두 가지 입니다.

- 가장 긴 root - left 경로 

    ▷ 트리의 높이에 해당

- 가장 긴 leaf - leaf 경로

    ▷ 각 서브트리의 높이를 계산한 뒤, 가장 높은 두 개의 서브트리를 선택

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
 
int C, N, longest;
int x[101], y[101], radius[101];
struct Tree {
    vector<Tree*> children;
};
 
// 성벽 a가 성벽 b를 포함하는지 확인
bool enclose(int a, int b) {
    if (radius[a] > radius[b]) {
        int dx = x[a] - x[b], dy = y[a] - y[b];
        // 두 성벽(원)의 중점간 거리의 제곱
        double diffOfRadius = pow(dx, 2) + pow(dy, 2);
        // 두 성벽의 반지름 차이의 제곱
        double distOfCenter = pow(radius[a] - radius[b], 2);
        if (diffOfRadius < distOfCenter)
            return true;
    }
    return false;
}
 
bool isChild(int parent, int child) {
    if (!enclose(parent, child))
        return false;
    // 두 성벽사이에 다른 성벽이 있는지 확인
    // 즉, 직계 부모-자식 관계인지 확인
    for (int i = 0; i < N; i++) {
        // 부모도 자식도 아닌 성벽(노드, 원)이 부모 노드에 포함되면서, child를 포함하는지 확인
        if (i != parent && i != child && enclose(parent, i) && enclose(i, child))
            return false;
    }
    return true;
}
 
//root 성벽을 루트로 하는 트리를 생성
Tree* getTree(int root) {
    Tree* tmp = new Tree();
    for (int i = 0; i < N; i++) {
        if (isChild(root, i)) {
            // ch 성벽이 root 성벽에 직접적으로 포함되어 있다면
            // 트리를 만들고 자손 목록에 추가한다
            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());
    // 서브트리 개수가 2개 이상인지 확인
    if (heights.size() >= 2)
        // 오름차순 정렬 했으므로, 가장 큰 높이 2개 추출
        longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights.size() - 1]);
    // 만약 서브트리가 1개 였다면 트리의 높이+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] >> radius[i];
        }
        Tree* T = getTree(0);
        cout << solve(T) << endl;
    }
    return 0;
}