FORTRESS 문제 질문 드립니다..

  • ggabu420
    ggabu420

    #include <iostream>
    #include <vector>
    #include <cmath>
    
    using namespace std;
    
    typedef struct _Tree
    {
        int x,y,r;
        vector<struct _Tree *> child;
    }Tree;
    
    vector<int> x,y,r;
    int rx,ry,rr,idx;
    
    int fortress(int);
    Tree *GenerateTree(int);
    void ReleaseTree(Tree*);
    int GetMaxDepth(Tree*,int);
    int  Recursion(Tree*);
    bool inCircle(int,int,int,int,int,int);
    
    int main()
    {
        int i,j;
        int c,n,t;
    
        cin >> c;
        for( i = 0; i < c; i++ ){
            cin >> n;
            for( j = 0; j < n; j++ ){
                cin >> t;
                x.push_back(t);
                cin >> t;
                y.push_back(t);
                cin >> t;
                r.push_back(t);
            }
            cout << fortress(n) << endl;
        }
        return 0;
    }
    int fortress(int n)
    {
        Tree *head;
        int i,rn,tn;
        int ix,mx1,mx2;
    
        head = GenerateTree(n);
        rn = head->child.size();
    
        mx1 = GetMaxDepth(head,0)-1;
        ix = idx;
        for( i = mx2 = 0; i < rn; i++ ){
            if( i == ix ) continue;
            tn = GetMaxDepth(head->child[i],0);
            if( mx2 < tn ) mx2 = tn;
        }
    
        idx = 0;
        ReleaseTree(head);
        return mx1+mx2;
    }
    int GetMaxDepth(Tree *tr, int dep)
    {
        int i,n,ret;
        int depth;
    
        n = tr->child.size();
        depth = 0;
    
        for( i = 0; i < n; i++ ){
            ret = GetMaxDepth(tr->child[i],dep+1);
            if( depth < ret ){
                depth = ret;
                if( !dep ) idx = i;
            }
        }
        return depth+1;
    }
    Tree *GenerateTree(int n)
    {
        int i,tidx,mx;
        Tree *head;
    
        head = new Tree;
        for( i = mx = 0; i < n; i++ ){
            if( mx < r[i] ){
                mx = r[i];
                tidx = i;
            }
        }
    
        head->x = x[tidx];
        head->y = y[tidx];
        head->r = r[tidx];
        head->child.clear();
        x.erase(x.begin()+tidx);
        y.erase(y.begin()+tidx);
        r.erase(r.begin()+tidx);
    
        for( i = 0; i < n-1; i++ ){
            rx = x[i];
            ry = y[i];
            rr = r[i];
            Recursion(head);
        }
    
        x.clear();y.clear();r.clear();
        return head;
    }
    void ReleaseTree(Tree *tr)
    {
        int i,n;
    
        n = tr->child.size();
        for( i = 0; i < n; i++ )
            ReleaseTree(tr->child[i]);
    
        delete tr;
    }
    int Recursion(Tree *tr)
    {
        int i,n,ret;
        Tree *t;
    
        if( inCircle(rx,ry,rr,tr->x,tr->y,tr->r) ){
            n = tr->child.size();
            for( i = 0; i < n; i++ ){
                ret = Recursion(tr->child[i]);
                if( ret == 1 ) return 1;
                else if( ret == 2 ){
                    t = new Tree;
                    t->x = rx;
                    t->y = ry;
                    t->r = rr;
                    t->child.push_back(tr->child[i]);
                    tr->child.erase(tr->child.begin()+i);
                    tr->child.push_back(t);
                    return 1;
                }
            }
            t = new Tree;
            t->x = rx;
            t->y = ry;
            t->r = rr;
            t->child.clear();
            tr->child.push_back(t);
            return 1;
        }
        else if( inCircle(tr->x,tr->y,tr->r,rx,ry,rr) ) return 2;
    
        return 0;
    }
    bool inCircle(int x1, int y1, int r1, int x2, int y2, int r2)
    {
        double t;
    
        if( r1 >= r2 ) return false;
        else{
            t = sqrt( (double)(((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1))) );
            if( (double)r2 > t ) return true;
        }
        return false;
    }
    

    FORTRESS 문제를 풀고 있습니다만...
    여러 예시를 만들어서 테스트해보고 다 해서 되는걸 확인했고
    알고리즘 상으로도 딱히 문제는 없어보이는데
    왜인지 굉장히 빠른 시간에 오답이 나서... 며칠간 고민해봤지만
    사실 떠오르지가 않네요.

    어떤 예시에서 문제가 발생했는지라도 하나만 알면
    고칠 수 있을 것 같은데 도저히 못 고치겠네요...혹시
    틀린 부분이 있을 것 같거나 아니면 틀린 예시라도 부탁드립니다..
    더이상은 이 문제에 시간을 쓰기도 힘드네요 ;; 풀것도 많은데..


    5년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    이거는 책에 보면 제가 설명해 둔 경우입니다만, 트리에서 가장 긴 경로는 두 잎 노드 사이에만 있는 것이 아닙니다. 다른 경우도 있으니 한번 생각해 보세요.


    5년 전 link
  • ggabu420
    ggabu420

    아.. 제가 다른 사람 얘기만 듣고 제 스스로 생각을 못했네요.
    제일 처음 생각했었던 게 맞았었는데.. 감사합니다.


    5년 전 link
  • 댓글을 남기시려면 로그인하세요.