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;
}

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

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


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

    아 깨달앗네요.. ㅎㅎ


    9년 전 link
  • hahanbyul
    hahanbyul

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


    7년 전 link
  • hahanbyul
    hahanbyul

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


    7년 전 link

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