FORTRESS

두 원의 좌표와 반지름을 통해 포함관계를 확인하여 트리를 만들어 최고 긴 노드간의 길이를 구하면 된다. 최대 길이는 트리의 깊이나 두 리프노드간의 길이가 된다는 점을 깨달아야 풀 수있는 문제.

가장 긴 두 개의 길이를 뽑아낼때 잘못짜서 개고생함

int n1 = 0, n2 = 0;
for (int a : heights) {
    if (a > n1) {
        n2 = n1;
        n1 = a;
    }
        // 뒤에 이 else if문이 없으면 최대 길이 이후에 나오는 길이는 죄다 무시됨
    else if (a > n2) {
        n2 = a;
    }
}

• 나의 풀이

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int sqr(int x) {
    return x * x;
}

class Wall {
public:
    int x, y, r, idx;
    vector<Wall*> child;

    Wall(const int _x, const int _y, const int _r) {
        this->x = _x;
        this->y = _y;
        this->r = _r;
    }
};

bool isParentNode(Wall* child, Wall* parent) {
    return child->r < parent->r &&
        sqr(child->x - parent->x) + sqr(child->y - parent->y) < sqr(child->r - parent->r);
}

int getHeight(Wall* n, int& longest) {
    vector<int> heights;
    if (n->child.empty()) {
        return 0;
    }
    for (Wall* cn : n->child) {
        heights.push_back(getHeight(cn, longest));
    }
    int n1 = 0, n2 = 0;
    for (int a : heights) {
        if (a > n1) {
            n2 = n1;
            n1 = a;
        }
        else if (a > n2) {
            n2 = a;
        }
    }
    if (heights.size() >= 2) {
       longest = max(longest, 2 + n1 + n2);
    }
    return n1 + 1;
}

bool cmp(const Wall* a, const Wall* b) {
    return a->r < b->r;
}

Wall* getNodeTree(vector<Wall*>& nodes) {
    sort(nodes.begin(), nodes.end(), cmp);
    for (int i = 0; i < nodes.size() - 1; i++) {
        for (int j = i + 1; j < nodes.size(); j++) {
            if (isParentNode(nodes[i], nodes[j])) {
                nodes[j]->child.push_back(nodes[i]);
                break;
            }
        }
    }

    return nodes.back();
}

int solve(Wall* root) {
    int longest = 0;
    int h = getHeight(root, longest);

    return longest < h ? h : longest;
}

int main() {
    int C, N, x, y, r;
    cin >> C;
    while (C--) {
        cin >> N;
        vector<Wall*> nodes(N);
        for (int i = 0; i < N; i++) {
            cin >> x >> y >> r;
            nodes[i] = new Wall(x, y, r);
        }
        Wall* n = getNodeTree(nodes);
        cout << solve(n) << "\n";
        /*for (auto a : nodes) {
            delete a;
        }*/
    }
}