21장 요새 FORTRESS

#include<iostream>
#include<string>
#include<vector>
#include<cassert>
#include<algorithm>
#include<queue>
#include<functional>
#include<random>
using namespace std;
 
struct TreeNode {
    vector<TreeNode*> children;
};
//지금까지 찾은 가장 긴 잎-잎의 경로의 길이를 저장.
int longest;
//입력 데이터
int n, y[100], x[100], radius[100];
//x^2를 반환
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) {
    //원을 포함하는 걸 확인 하는 공식 (x1-x2)^2+(y1-y2)^2<(r1-r2)
    return radius[a] > radius[b] && sqrdist(a, b) < sqr(radius[a] - radius[b]);
}
//'성벽' 트리에서 parent가 child의 부모인지 확인한다.
//parent는 child를 꼭 직접 포함해야 한다.
bool isChild(int parent, int child) {
    if (!encloses(parent, child))
        return false;
 
    for (int i = 0; i < n; i++) {
        //parent에포함된 원 i, 원 i에 포함된 원 child의 관계가 성립되면
        //직접포함관계가 아니라 간접포함관계이므로 false를 return 한다.
        if (i!=parent && i != child && encloses(parent, i) && encloses(i, child))
            return false;
    }
    return true;
}
 
 
 
//root를 루트로 하는 서브트리의 높이를 반환한다.
int height(TreeNode* root) {
    vector<int> heights;
    for (int i = 0; i < root->children.size(); i++)
        heights.push_back(height(root->children[i]));
    //만약 자식이 하나도 없다면 0을 반환.
    if (heights.empty()) return 0;
 
    sort(heights.begin(), heights.end());
    //정렬했으므로 heights[heights.size() - 2](2번째로 큰 높이) heights[heights.size() - 1](1번째로 큰 높이)
    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);
}
 
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(void) {
    int cases;
    cin >> cases;
    while (cases--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> x[i] >> y[i] >> radius[i];
        TreeNode* root = getTree(0);
        cout << solve(root) << endl;
 
    }
    return 0;
}

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

책 표기에는 난이도가 중이라고 되어있지만 정말 해결하기 힘든 문제였다. 문제해결방법은 떠올릴 수 있었으나 (그래서 난이도가 중??)

그것을 이렇게 언어로 구현하는 것 자체가 매우 어려워서 실패했다.

본인은 처음 문제를 풀으려고 시도했을때 

struct circle{

int x;

int y;

int radius;

};

라는 구조체를 만들어서 한번에 함수에 모든 정보를 다 보내려고 했었는데, 일단 책의 함수와 똑같이 구현하는 방법을 

더 연습해보고 처음 시도했던 저 방법으로 다시 구현해보고 코딩내용을 추가 수정해봐야겠다...

문제를 봤을때 대충 어떻게 접근해야 하는지 감이 잡혔으나 도저히 구현할 수 가 없었다. 

그리고 최장 경로의 길이가 두가지 경우가 있음에도 본인은 2번의 경우밖에 떠올리지 못했다.

1.가장 긴 루트-잎 경로의 길이

2.가장 긴 잎-잎 경로의 길이

1번의 예외를 놓치기 쉬울 것 같다. 조심하자.