dygks232   4달 전

어떤 트리에서 a노드와 b노드의 경로의 길이를 구하는

1. 각 노드의 depth를 비교

2. 두 노드의 depth가 같을때까지 더 깊이있는 노드를 부모로 올리면서, 간선의 가중치를 계속 더한다.

3. 두 노드의 depth가 같아졌어도 두 노드가 서로 다른노드라면, 두 노드 모두 부모로 올려가면서, 간선의 가중치를 계속 더한다.

4. 두 노드가 같은 노드가 되면 중지한다.

라는 알고리즘과,


어떤 트리에서 경로의 길이가 최대가 될 때 두 노드는 모두 leaf노드이다.


라는 원리를 이용해서 트리에서 최대경로의 길이를 구해야하는 이 문제를 풀어봤는데요....


입력의 조건에 맞게 모두 구현한거 같은데 틀렸습니다가 뜨네요...

코드설명은 주석에 달아놨습니다ㅠㅠ 이 문제좀 해결좀해주세요...

ntopia   4달 전

"어떤 트리에서 경로의 길이가 최대가 될 때 두 노드는 모두 leaf노드이다."

라고 하셨는데, 이게 맞지 않는 경우가 있습니다.

바로 루트의 자식이 1개 뿐일 때 입니다.

예를 들면 일자모양인 트리가 있겠죠.

이런 경우에는 루트도 비교후보 중 하나로 삼아야 합니다.

dygks232   4달 전

와.... 그생각을못했네요... 그부분은 예외처리하고 다시 시도해보겠습니다ㅠㅜ 감사합니다

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