suno   6달 전

노드를 preorder로 순회하면서 각 노드에서 리프까지의 최장 경로 거리를 계산하고, 지름을 갱신합니다.

각 노드의 '리프까지의 최장 경로 거리'는 (자식의  '리프까지의 최장 경로 거리' + 자식의 '이 노드까지의 거리')의 최댓값으로 계산합니다.

같은 방식으로 '리프까지의 두 번째로 긴 경로 거리'를 계산합니다.

지름이  '리프까지의 최장 경로 거리'' +  '리프까지의 두 번째로 긴 경로 거리'보다 작으면 지름을 갱신합니다.

(단, 자식이 하나면 '리프까지의 최장 경로 거리'만으로 지름을 갱신합니다.)

이렇게 하면 직선으로 이루어진 트리의 지름을 포함해 모든 경우의 최대 지름을 구할 수 있을 것 같은데, 구현한 코드를 수행하면 0%부터 틀렸다고 뜹니다.

예시와 제가 생각한 결과들, 질문 게시판의 반례들은 통과합니다.

방법이 잘못된 건가요? 아니면 구현이 잘못된 걸까요?

도움을 구합니다ㅜㅜ

luniro   6달 전

반례드립니다

입력:
4
1 2 3
1 3 4
2 4 9
2 5 9
출력:
16
정답:
18

suno   6달 전

답변 감사합니다.

그런데 "파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다."라고 했으니 입력 첫째 줄이 5가 되어야 하는 것 아닌가요?

입력을 5로 바꾸면 정답을 출력합니다.

sait2000   6달 전

53번 줄이 틀렸습니다. 새로 가장 큰 게 있으면 전에 가장 컸던 거는 이제 두번째로 큰 게 되겠죠.

suno   6달 전

답변 감사합니다!

두 번째로 큰 것도 같이 갱신해야 한다는건 전혀 생각 못했네요..

감사합니다!

그래도 27%에서 에러가 뜨는데 또 찾아봐야겠네요..

luniro   6달 전

앗 그러네요 죄송합니다ㅠ

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