FORTRESS 제 알고리즘이 왜 틀린지 모르겠습니다. 100프로 맞다고 생각했는데..

  • dookim123
    dookim123
    • 제가 풀고 있는 문제는 FORTRESS입니다. 해당 문제에서 제 알고리즘이 뭐가 틀린지 모르겠습니다. 알고리즘은 트리를 만드는 알고리즘과 최대길이를 구하는 알고리즘으로 구성되어있습니다. 문제의 링크 -> 문제

    트리를 만드는 알고리즘

    • 트리를 만드는 알고리즘은 최초로 성벽의 반지름을 기반으로 내림차순으로 정렬합니다.
    • 내림차순을 하는 이유는 삽입될 노드는 삽입되어있는 노드의 부모가 절대 될 수 없기 때문입니다.(부모는 자식보다 무조건 반지름이 크기 때문입니다.) ( 따라서 삽입하려는 노드는 현재 노드의 자식이거나 노드의 자식의 자식인 경우밖에 없습니다.) -아래는 위의 설명을 나타낸 코드입니다.
    //children의 자식이거나 그것이 아니라면 나의 자식이다.
    //children의 자식이면 재귀함수를 사용
        void insert(Node & node) {
            if(children.size() == 0) {
                children.push_back(node);
                return;
            }
            for(int i = 0; i < children.size(); i++) {
                if(isChild(children[i], node)) {
                    children[i].insert(node);
                    return;
                }
            }
            //만약 자식 관계가 아니라면 현재노드의 자식으로 둔다.
            children.push_back(node);
        }
    

    최대 길이를 구하는 알고리즘

    • 최대길이는 루트노드에서 자식 노드들의 높이를 구합니다.
    • 자식노드들의 높이를 내림차순으로 정렬하고 가장 상위의 두개를 더합니다. (자식 노드가 하나라면 하나를 출력합니다. 아래는 해당 소스코드입니다.)
        //트리의 높이를 구하는 함수
        int getTreeDepth() {
            //base condition
            if(children.size() == 0) return 1;
            int max = -1;
            for(int i = 0; i < children.size(); i++) {
                int childTreeDepth = children[i].getTreeDepth();
                if(max < childTreeDepth) {
                    max = childTreeDepth;
                }
            }
            return 1 + max;
        }
    
        //루트노드의 모든 차일드의 높이를 구하는 함수
        //각 자식의 높이를 구해 vector를 리턴합니다.
        vector<int> getChildrenTreeDepth() {
            vector<int> childrenTreeDepthes;
            for(int i = 0; i < children.size(); i++) {
                childrenTreeDepthes.push_back(children[i].getTreeDepth());
            }
            return childrenTreeDepthes;
        }
    

    전체 소스코드

    //
    //  main.cpp
    //  yose
    //
    //  Created by dookim on 4/1/15.
    //  Copyright (c) 2015 dookim. All rights reserved.
    //
    
    #include <iostream>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    using namespace std;
    
    class Node {
    public:
        vector<Node> children;
        int x;
        int y;
        int r;
        Node(int x, int y, int r): x(x), y(y), r(r) {}
    
        //children의 자식이거나 그것이 아니라면 나의 자식이다.
        void insert(Node & node) {
            if(children.size() == 0) {
                children.push_back(node);
                return;
            }
            for(int i = 0; i < children.size(); i++) {
                if(isChild(children[i], node)) {
                    children[i].insert(node);
                    return;
                }
            }
            //만약 자식 관계가 아니라면 현재노드의 자식으로 둔다.
            children.push_back(node);
        }
    
        bool isChild(Node & parent, Node & child) {
            double distance = sqrt(pow((parent.x - child.x),2) + pow((parent.y - child.y),2));
            return abs(parent.r - child.r) > distance;
        }
    
        //트리의 높이를 구하는 함수
        int getTreeDepth() {
            //base condition
            if(children.size() == 0) return 1;
            int max = -1;
            for(int i = 0; i < children.size(); i++) {
                int childTreeDepth = children[i].getTreeDepth();
                if(max < childTreeDepth) {
                    max = childTreeDepth;
                }
            }
            return 1 + max;
        }
    
        //루트노드의 모든 차일드의 높이를 구하는 함수
        //각 자식의 높이를 구해 vector를 리턴합니다.
        vector<int> getChildrenTreeDepth() {
            vector<int> childrenTreeDepthes;
            for(int i = 0; i < children.size(); i++) {
                childrenTreeDepthes.push_back(children[i].getTreeDepth());
            }
            return childrenTreeDepthes;
        }
    
    
    };
    /*
    
    3
    3
    5 5 15
    5 5 10
    5 5 5
    8
    21 15 20
    15 15 10
    13 12 5
    12 12 3
    19 19 2
    30 24 5
    32 10 7
    32 9 4
    8
    21 15 20
    15 15 10
    13 12 5
    12 12 3
    19 19 2
    30 24 5
    32 10 7
    32 9 4
    
     */
    //내림차순으로 정렬하는것!
    bool compare (const Node& node1, const Node& node2) {
        return (node1.r > node2.r);
    }
    
    int main(int argc, const char * argv[]) {
        // insert code here...
        int testcase;
        scanf("%d", &testcase);
    
        for(int testIndex = 0; testIndex < testcase; testIndex++) {
            int nodeNum;
            scanf("%d", &nodeNum);
            vector<Node> nodes;
            for(int nodeIndex = 0; nodeIndex < nodeNum; nodeIndex++) {
                int x;
                int y;
                int r;
                scanf("%d", &x);
                scanf("%d", &y);
                scanf("%d", &r);
                Node node(x,y,r);
                nodes.push_back(node);
            }
            std::sort(nodes.begin(), nodes.end(), compare);
            Node & root = nodes[0];
            for(int i = 1; i < nodes.size(); i++) {
                root.insert(nodes[i]);
            }
            vector<int> depthes = root.getChildrenTreeDepth();
            if(depthes.size() == 1) {
                cout<<depthes[0]<<endl;
            } else if(depthes.size() >= 2){
                std::sort(depthes.begin(), depthes.end(), greater<int>());
                int answer = depthes[0] + depthes[1];
                cout<<answer<<endl;
            } else {
                throw 100;
            }
        }
    
    
        return 0;
    }
    

    아무리 생각해도 알고리즘 상으로 뭐가 틀린지 모르겠습니다.

    질문들어주셔서 감사합니다!


    6년 전
3개의 댓글이 있습니다.
  • dookim123
    dookim123

    아 깨달앗네요.. ㅎㅎ


    6년 전 link
  • hahanbyul
    hahanbyul

    뭐가 문제였나요? 깨달은 점도 써주시지..


    4년 전 link
  • hahanbyul
    hahanbyul

    해결했습니다. 저의 경우에는 가장 긴 경로의 패스를 찾는 것이 잘못되었었습니다. 잎과 잎 사이의 패스와 트리의 높이 중 가장 긴걸 찾았어야 했네요.


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