k123s456h   1년 전

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

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의 가중치 = 트리의 지름이다.

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

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

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

k123s456h   1년 전

반례

8

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

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