글 읽기 - 제 알고리즘이 어디가 잘못되었는지 궁금합니다.

k123s456h 3년 전 0

다른 정답글에서 사용된 알고리즘은

1. 임의의 노드 x에서 가장 먼 노드 a를 찾는다.

2. 노드 a에서 가장 먼 노트 b를 찾는다.

3. 트리의 지름은 노드 a에서 노드 b사이의 거리이다.

인데

저는 이렇게 생각했습니다.

1. 주어진 트리에서 가중치가 가장 큰 간선 x를 찾고 양 끝 노드를 a, b라 한다.

2. 노드 a와 연결된 방문하지 않은 sub graph중에서 가중치가 가장 큰 그래프를 선택한다.

3. 노드 b에 대해서도 2와 같은 방식으로 계산한다.

4. 간선 x의 가중치 + 노드 a에 연결된 sub graph의 가중치 + 노드 b에 연결된 sub graph의 가중치 = 트리의 지름이다.

어느 부분이 잘못되었는지 알려주시면 감사하겠습니다.

반례만이라도 알려주시면 좋겠습니다.

나름대로 구현한 코드도 첨부합니다.

#include <iostream>
#include <vector>
using namespace std;
int maxWeight(vector<pair<int, int>> graph[], int root, bool isVisited[])
{
  int weight = 0;
  for (auto it = graph[root].begin(); it != graph[root].end(); it++)
  {
    if(!isVisited[it->first]){
      isVisited[it->first] = true;
      weight = max(weight, it->second + maxWeight(graph, it->first, isVisited));
    }
  }
  return weight;
}
int main(void)
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  int diameter = 0;
  cin >> n;

  vector<pair<int, int>> graph[n + 1];
  bool isVisited[n + 1] = {
      false,
  };
  int startHead, startTail, startWeight = 0;

  for (int i = 0; i < n; i++)
  {
    int root, child, distance;
    cin >> root >> child;
    while (child != -1)
    {
      cin >> distance;
      if (distance > startWeight)
      {
        startHead = root;
        startTail = child;
        startWeight = distance;
      }
      graph[root].push_back(make_pair(child, distance));
      cin >> child;
    }
  }

  isVisited[startHead] = true;
  isVisited[startTail] = true;
  diameter = startWeight + maxWeight(graph, startHead, isVisited) + maxWeight(graph, startTail, isVisited);

  cout << diameter << '\n';

  return 0;
}

k123s456h 3년 전 0

반례

1 2 1 -1

2 1 1 3 1 -1

3 2 1 4 1 -1

4 3 1 5 1 8 2 -1

5 4 1 6 1 -1

6 5 1 7 1 -1

7 6 1 -1

8 4 2 -1

answer = 6

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

문제

문제

출처

ICPC

제 알고리즘이 어디가 잘못되었는지 궁금합니다.

k123s456h 3년 전 0

k123s456h 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말