요새(FORTRESS) 문제에 트리 노드 삽입 알고리즘 틀린부분이 어디일까요?

  • tjkim
    tjkim

    요새(FORTRESS) 문제를 풀고 있는데
    노드 삽입 하는 부분에서 틀렸습니다.
    (노드 삽입 부분을 알고리즘 문제해결 전략 책에 나온
    알고리즘과 비슷하게 바꾸면 정상 동작합니다.)

    책에서는 전체 입력을 받은 후
    상위 노드와 하위 노드 사이에 들어가는 노드가 있는지
    확인후 삽입하는 형태였습니다. (여기서 노드는 성벽입니다.)

    제 생각에는 부모 노드에 자식노드를 삽입 할때마다
    부모의 하위에 있는 노드를 확인하여
    삽입 되는 자식 노드의 하위에 있으면
    그쪽으로 이동하면 된다고 생각하여 작성한 알고리즘입니다.

    bool Insert(Node* parent, Node* child)
    {
    bool bResult = false;

    //자식 노드가 부모노드 안에 포함됨
    //반환값 : 포함되면 ture , 포함되지 않으면 false
    if(Inclusion(parent, child))
    {
        int iChildrenCount = parent->children.size();
    
        for(int i = 0 ; i < subCount ; ++i)
        {
            //재귀로 하위에 삽입되는 노드를 찾는다.
            // 반환값 : 하위에 삽입되면 true
            //           : 삽입 실패 시  false
            bResult = Insert(parent->children[i],sub);
        }
    
        //하위 노드에 삽입 실패 시 현재 노드에 삽입
        if(!bResult)
        {
            //자식 노드를 부모 노드에 집어 넣음
            parent->children.push_back(sub);
            //자식 노드의 부모를 부모노드로 설정
            sub->parent = parent;
    
            //부모 노드에서 하위노드로 이동된 노드 개수
            int moveCount = 0; 
    
            //현재 부모 노드의 하위에 있는 
            //노드 중 (children에 있는 노드 중)
            //자식 노드에 포함되어 자식노드의 
            //하위 노드로 가야하는 노드를 찾아 변경
            for(int j = 0 ; j < subCount - moveCount ; ++j)
            {
                //자식 노드에 포함 되는 부모노드의 하위 노드
                if(Inclusion(sub, parent->children[j]))
                {   
                    //자식 노드에 포함되는 부모의 하위 노드 삽입
                    sub->children.push_back(parent->children[j]);
                    parent->children[j]->parent = sub;
    
                    //부모 노드에서 자식노드로 이동된 노드 삭제
                    parent->children.erase(
                          parent->children.begin()+j);
                    //부모 노드의 하위 노드를 삭제하여
                    //부모의 하위 개수 변경되어 
                    //현재 위치에서 다시 확인
                    --j;
                    ++moveCount;
                }
            }
            bResult = true;
        }
    }
    return bResult;

    }

    //부모 노드에 자식노드가
    //포함되어있는지 확인
    bool Inclusion(Node* parent, Node* child)
    {
    bool bResult = false;

    if(parent->r > child->r)
    {
        double dX = (double)(parent->x - child->x);
        double dY = (double)(parent->y - child->y);
        double dR = pow(dX,2) + pow(dY,2);
    
        double dParentR = pow((double)(parent->r - child->r),2);    
        if(dR < dParentR)
        {
            bResult = true;
        }
    }
    return bResult;

    }

    struct Node
    {
    int x;
    int y;
    int r;
    Node* parent;
    vector children;
    };

    혹시 보시고 틀린부분이나
    틀리는 테스트 케이스가 있으면
    알려주시면 감사하겠습니다.


    9년 전
4개의 댓글이 있습니다.
  • 샥후
    샥후

    Inclusion함수내에서 sub가 정의되지 않았네요.


    9년 전 link
  • tjkim
    tjkim

    지적 감사합니다.
    소스코드 올리기전에 변수명을 sub 에서 child로 변경해서 보기 쉽게하다는것이 실수했내요..
    대답이 늦어 죄송합니다.


    9년 전 link
  • 샥후
    샥후

    sub, child간 혼용이 많은데... 그 부분을 제외하고 보자면
    bResult = Insert(parent->children[i],sub);
    이 부분이 항상 마지막 노드의 결과값만을 가지게되네요.


    9년 전 link
  • tjkim
    tjkim

    정말 감사합니다!!!
    저부분이 잘못된 것이였습니다.
    저부분을 수정하니 정답으로 나오는군요
    도움에 정말로 감사드립니다.


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