알고스팟 (algospot) FORTRESS

못풀었다.

종만북 코드를 이해하고 책을 보지않고 따라해보았다.

leaf에서 leaf까지의 최대값과 leaf에서 root까지의 최대값의 최대값이 정답이 되는것으로 나눈것을 생각하지 못했다. 더 깊이 생각하는 습관을 가져야겠다.

트리 탐색시 다음노드들의 리턴값을 벡터에 저장하여 높이를 뽑아내는 패턴도 기억 해야겠다는 생각을 했다.

트리 탐색 기본 구조도 익혔고, 트리 생성 기본 구조도 익힐 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Pair{
    int y;
    int x;
    int r;
};
struct TreeNode{
    vector<TreeNode*> children;
};
 
 
Pair wall[101];
int longest;
int N, T;
 
int sq(int x){
    return x * x;
}
bool enclose(int a, int b){
    if(wall[a].r <= wall[b].r) return false;
 
    int y1 = wall[a].y;
    int x1 = wall[a].x;
    int r1 = wall[a].r;
    int y2 = wall[b].y;
    int x2 = wall[b].x;
    int r2 = wall[b].r;
    if(sq(r1 - r2) <= sq(x1 - x2) + sq(y1 - y2)){
        return false;
    }
    return true;
}
 
bool isChild(int parent, int child){
    if(parent == child) return false;
    if(!enclose(parent, child)) return false;
    for(int i = 0 ; i < N; i++){
        if(i == parent || i == child) continue;
        if(enclose(parent, i) && enclose(i, child)) return false;
 
    }
    return true;
}
TreeNode* getTree(int root){
    TreeNode* node = new TreeNode();
    for(int i = 0 ; i < N; i++){
        if(isChild(root, i)){
            node->children.push_back(getTree(i));
        }
    }
 
    return node;
}
 
 
int height(TreeNode* root){
    int s = root->children.size();
    vector<int> heights;
    for(int i = 0 ; i < s; i++){
        heights.push_back(height(root->children[i]));
    }
    if(heights.empty()) return 0;
    int h_s = heights.size();
    if(h_s >= 2){
        sort(heights.begin(), heights.end());
        longest = max(longest, heights[h_s - 1] + heights[h_s - 2] + 2);
    }
    return heights.back() + 1;
}
bool cmp(Pair a, Pair b){
    if(a.r < b.r) return false;
 
    return true;
}
 
int main(void){
    scanf("%d", &T);
    while(T--){
        longest = 0;
        scanf("%d", &N);
        for(int i = 0 ; i < N; i++){
            int x, y, r;
            scanf("%d %d %d", &x, &y, &r);
            wall[i] = {y, x, r};
        }
 
        sort(wall, wall + N, cmp);
 
 
        TreeNode* root = getTree(0);
        printf("%d\n", max(longest, height(root)));
    }
}