kioio5   4년 전

제 알고리즘은 노드의 개수만큼 bfs를 하는 방법입니다.

우선 해당 노드에 연결되어 있는 자식노드의 개수만큼 for문을 이용하여 큐에 삽입합니다. 이 때 각각의 방향을 가지고 삽입을 합니다.

예를 들어 자식이 세명이면 0 1 2 이런식으로 방향을 삽입합니다.

그리고 각 방향에 대하여 최대길이를 구한다음 가장 긴 방향과 두번째로 긴 방향을 더한 후 리턴하는 방식입니다.

모든 노드에 대해서 한다면 최대길이가 나올 것이라고 생각했는데 예외가 있을까요???



어떤 임의의 노드에서 가장 먼 노드, 그리고 그 가장 먼 노드로부터 가장 먼 노드 사이의 거리가 지름이라는 알고리즘은 이미 찾아봐서 알고있습니다.


chogahui05   4년 전

이 데이터에 대해서 테스트 해 보시겠어요?

5

1 2 33

2 3 34

1 4 22

1 5 10

kioio5   4년 전

@chogahui05

감사합니다!!!!! 덕분에 반례 찾았습니다.
이진트리라고 가정하고 풀었었는데 아니었네요 ㅠㅠㅠㅠㅠ
그래서 left와 right로 풀었었는데
수정을 했습니다.
각 자식의 방향을 0~자식의 개수 - 1로 부여를하고
그 중에 최대값 두개를 선택하는 방식으로했습니다. 감사합니다.

rlaalswo01   3년 전

저도 이진트리라고 가정하고 풀었다가 이거 보고 해결 ... ㅎㅎ !

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