[도움요청] FORTRESS 문제 예외 케이스가 무엇이 있을까요?

  • realmind
    realmind

    질문에 포함되어야 할 내용

    FORTRESS 문제를 풀던 중 아래와 같이 테스트했는데, 어디서 잘못된 것인지 잘 모르겠습니다.

    문제는 아래와 같은 답일 것이라고 생각하고 풀었는데요.

    (tree의 높이) 이거나 (가장 긴 2개 subtree의 높이합)

    높이는 height()에서 구하고 longest는 child가 있을 때, 가장 큰 두 subtree의 높이합으로 height()에서 longest 전역변수에 값을 바로 업데이트 합니다.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    #define MAX_C   (100)
    #define MAX_N   (100)
    
    using namespace std;
    
    struct Tree {
        int r, x, y;
        vector<Tree*> children;
        bool operator <(const Tree &rside) const {
            return (r < rside.r);
        }
    };
    
    Tree trees[MAX_N];
    int longest = 0;
    
    bool enclose(int out, int in) {
        int x = trees[out].x - trees[in].x;
        int y = trees[out].y - trees[in].y;
        int r = trees[out].r - trees[in].r;
        return ((trees[out].r > trees[in].r) && (x*x + y*y < r*r));
    }
    
    Tree *makeTree(int n) {
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                if(enclose(j, i)) {
                    trees[j].children.push_back(&trees[i]);
                    break;
                }
            }
        }
    
        return &trees[n-1];
    }
    
    int height(Tree *root) {
        int h1 = -1, h2 = -1;
        for(Tree *child : root->children) {
            int ch = height(child);
            if(ch >= h1) {
                h2 = h1;
                h1 = ch;
            }
        }
    
        if(h2 >= 0) {
            longest = max(longest, h1 + h2 + 2);
        }
    
        return (h1 + 1);
    }
    
    int main(void) {
        int nTests, n;
        cin >> nTests;
    
        while(nTests--) {
            cin >> n;
            for(int i = 0; i < n; ++i) {
                cin >> trees[i].x >> trees[i].y >> trees[i].r;
                trees[i].children.clear();
            }
            sort(trees, trees + n);
    
            Tree *root = makeTree(n);
            longest = -1;
            int h = height(root);
            cout << max(h, longest) << endl;
        }
    
        return 0;
    }
    

    제가 놓치고 있는 예외케이스가 있을 것으로 판단되는데요.
    어떤 예외케이스가 있을까요?


    8년 전
2개의 댓글이 있습니다.
  • astein
    astein

    케이스의 문제가 아니라, 구현상의 문제로 보입니다

    int height(Tree *root) 구현에서
    트리의 차일드가 3 이상일때 문제가 발생할 수 있습니다.


    8년 전 link
  • realmind
    realmind

    astein 님 좋은 조언 감사합니다 :)
    괜히 이상한 최적화를 하려고 하다가 문제가 발생했네요.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.