글 읽기 - 문제를 틀렸는데 어떤 부분이 잘못된 걸까요?

lvhi0607 2년 전 0

해결을 위해 다음 방식을 이용했습니다.

1. 트리를 구성한다(루트 노드가 1번으로 고정되어 있으며 부모 노드의 번호가 낮은 순으로, 부모 번호가 같은 경우 자식 노드 번호가 낮은 순으로 주어지므로, 주어지는 순서대로 트리를 차근차근 구성해도 될 것으로 예상)

트리를 구성할 때, 노드 번호를 인덱스로 하는 노드 배열을 구성해 언제든 해당 번호 노드에 접근할 수 있도록 함

2. 트리 구성이 완료된 경우 노드 배열을 순회하여 리프 노드들을 찾아 leaf 컨테이너에 추가. 자식 노드가 없는 경우 리프 노드로 간주함.

3. 리프 노드들을 이중 반복문으로 순회하며 임의의 두 노드를 선택해 두 노드들의 공통 조상까지의 거리 합(두 노드 간의 거리)을 구함.

(공통 조상까지의 거리 합을 위해 노드를 구성할 때 루트 노드부터 자신까지의 가중치를 저장하도록 설정, 이후 공통 조상까지의 거리는 자신이 갖고 있는 가중치 - 공통 조상의 가중치 를 이용)

4. 3에서 구한 거리 합 중 최댓값을 정답으로 출력.

인데 예시는 정답을 출력하지만 문제는 틀렸다고 나옵니다. 따로 반례가 떠오르지 않는데, 접근하는 과정에서 문제가 있었던 걸까요? 도움 부탁드립니다..

#define _CRT_SECURE_NO_WARNINGS
#define MAXN 10001

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Node
{
    Node* parent = nullptr;
    vector<Node*> child;
    int weight = 0;
    int depth = 0;

    Node* get(Node* parent, int weight)
    {
        this->parent = parent;
        this->parent->child.push_back(this);
        this->weight = weight + parent->weight;
        this->depth = parent->depth + 1;

        return this;
    }
}node[MAXN];

int main()
{
    int n;
    cin >> n;
    // Step 1. Set Node
	for (int i = 0; i < n - 1; i++)
    {
        int parent, child, weight;
        cin >> parent >> child >> weight;
        node[child].get(&node[parent], weight);
    }

    // Step 2. find Leaf Nodes
    vector<Node*> leaf;
	for (int i = 1; i <= n; i++)
    {
        if (node[i].child.empty())
        {
            leaf.push_back(&node[i]);
        }
    }

    // Step 3. Find answer;
    int answer = 0;

	for (int i = 0; i < leaf.size() - 1; i++)
    {
		for (int j = i + 1; j < leaf.size(); j++)
        {
            auto lptr = leaf[i];
            auto rptr = leaf[j];

            while (lptr->depth > rptr->depth)
            {
                lptr = lptr->parent;
            }
            while (rptr->depth > lptr->depth)
            {
                rptr = rptr->parent;
            }

            while (rptr != lptr)
            {
                lptr = lptr->parent;
                rptr = rptr->parent;
            }
            auto ancestorWeight = lptr->weight;
            auto result = leaf[i]->weight + leaf[j]->weight - (2 * ancestorWeight);

            answer = answer < result ? result : answer;
        }
    }
    cout << answer << endl;

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.