FORTRESS 문제 JUDGE 오류 신고합니다.

  • kwangswei
    kwangswei

    안녕하세요.
    FORTRESS 문제 오류 신고합니다.

    책에서도 언급되어 있다시피 해당 문제의 답은,
    1. root - leaf 노드 간 최장 경로
    2. leaf - leaf 노드 간 최장 경로
    둘 중 하나의 케이스가 됩니다.

    제가 문제를 풀 때 2번의 경우는 고려하지 못하고,
    1번 경우만 고려하여 문제를 푼 후 제출하였는데 ACCEPT 를 받았습니다.

    그 후 다시 풀어보면서 틀렸다는 것을 감지하고
    예제 데이터를 만들어서 넣어보니 실제로 답이 틀리게 나왔습니다.

    제 구현 소스는 아래와 같습니다.
    getMaxDistance() 함수를 보면 root.getMaxDistance() 를 호출하고,
    이는 1번 케이스의 답을 계산하게끔 되어 있습니다.
    Node::getMaxDistance() 를 보면 자기 자식의 level 만 고려하고 있습니다.

    그리하여 아래와 같은 예제를 넣어 돌려보면 답이 4가 나와야 하는데 root 에서부터 leaf 만 고려하므로 3이 나옵니다.

    1
    6
    15 15 100
    15 15 99
    5 15 3
    25 15 3
    5 15 2
    25 15 2

    (VOCList 님의 제보로 예제 고쳐놓았습니다.)

                       (15,15,100)
                        |
                   (15,15,99)
                      /      \
                (5,15,3)   (25,15,3)
                   |            |
                (5,15,2)    (25,15,2)

    확인 부탁 드립니다~

    #include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#include <cstdio>
using namespace std;

class Node
{
    public:
        int x;
        int y;
        int r;

        vector<Node> child;

        bool isMyChild(Node& node)
        {
            if ( sqrt( (x-node.x)*(x-node.x) + (y-node.y)*(y-node.y)) < (double)r )
                return true;
            return false;
        }

        int getMaxDistance()
        {
            vector<int> levels;
            for ( int i = 0; i < child.size(); i++ )
                levels.push_back( 1 + child[i].getLevel());

            if ( levels.empty())
                return 0;
            if ( levels.size() == 1 )
                return levels[0];
            sort(levels.begin(), levels.end(), greater<int>());
            return levels[0] + levels[1];
        }

        int getLevel()
        {
            int level = 0;
            for ( int i = 0; i < child.size(); i++ )
                level = max( level, 1+child[i].getLevel());
            return level;    
        }

        void addNode(Node node)
        {
            for ( int i = 0; i < child.size(); i++ )
            {
                if ( child[i].isMyChild(node))
                {
                    child[i].addNode(node);
                    return;
                }
            }
            child.push_back(node);
        }
};

bool nodeSortByRad(const Node& node1, const Node& node2)
{
    return node1.r > node2.r;
}

int getMaxDistance(vector<Node> allNodes)
{
    Node root = allNodes[0];

    for ( int i = 1; i < allNodes.size(); i++ )
        root.addNode(allNodes[i]);

    return root.getMaxDistance();
}

int main()
{
    int C;
    cin >> C;

    while ( C-- )
    {
        int T;
        cin >> T;

        vector<Node> allNode;
        for ( int i = 0; i < T; i++ )
        {
            Node node;
            cin >> node.x >> node.y >> node.r;
            allNode.push_back(node);
        }

        sort( allNode.begin(), allNode.end(), nodeSortByRad);

        cout << getMaxDistance(allNode) << endl;
    }
    return 0;
}

    11년 전
10개의 댓글이 있습니다.
  • Being
    Being

    그..그림이 예뻐서 추천!


    11년 전 link
  • kwangswei
    kwangswei

    Being / ㅋㅋㅋ 보기 쉽게 만들어야 Feedback 도 잘 올테니 신경 좀 썼습니다. ㅋㅋㅋ 다행히 코드 블럭을 쓰니 잘 나오네요!


    11년 전 link
  • VOCList
    VOCList

    좋아요


    11년 전 link
  • VOCList
    VOCList

    그런데 예시로 넣은 데이터는 입력하신 원끼리 겹치고 있는 데이터인 것 같습니다. (5, 15, 5)와 (10, 15, 5)는 거리가 5 떨어져 있는 원인데 두 원의 반지름이 둘다 5이기 때문에 이 원들이 겹치지 않으려면 10 이상 떨어지는 것이 맞을 것 같아요.
    그리고 10 이상 떨어뜨려서 kwangswei님 소스를 돌려보니 정답 4가 잘...


    11년 전 link
  • VOCList
    VOCList

    중심의 거리가 5 떨어져*


    11년 전 link
  • kwangswei
    kwangswei

    VOCList / 앗, 이런 바보 같은!! ㅋㅋ
    1
    6
    15 15 100
    15 15 99
    5 15 3
    25 15 3
    5 15 2
    25 15 2

    예제를 이렇게 만들어보면, (15,15) 를 중심으로 r=100 인 원 안에 바로 r=99 인 원이 들어가고,
    그 안에 (5,15) (25,15) 는 서로 20 만큼 떨어져 있으므로,
    r=3 인 원들이 서로 겹치지도 않으며, 그 안에 같은 중심을 갖는 r=2 인 원이 있으므로 이제 의도한 예제가 될 것 같습니다.

    돌려보니 3 나오네요.
    이거 은근 좌표 만들기 어렵군요 ㅋㅋㅋㅋ
    중고딩 때부터 도형이나 공간지각을 요구하는 문제들에 엄청 약했는데 ㅋㅋㅋ


    11년 전 link
  • kwangswei
    kwangswei

    참고로 소스를 2번 케이스도 고려하게끔 바꿔서 구현한 것에서는 정상적으로 4 가 잘 나옵니다. ㅎㅎ 제 소스는 문제 있는 소스가 맞는 것 같고, 이 것이 ACCEPT 되었으므로 저지 서버가 모든 케이스를 다 체크하지 못하는 것이 맞는 것 같습니다.


    11년 전 link
  • VOCList
    VOCList

    어 그르네요. 제가 아까 바꿔서 넣어봤을 땐 뭔가 4가 나왔었는데 저도 만들면서 실수했나봐요 지금 해보니 3이...
    ㄲㄲㄲ


    11년 전 link
  • JongMan
    JongMan

    훌륭한 운영진 누가 좀 고쳐주세여 [...] ㅜㅜ


    11년 전 link
  • kcm1700
    kcm1700

    데이터 추가하고 재채점 했습니다. 혹시 이상이 있는 것 같으면 알려주세요.


    11년 전 link

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