wwiiiii   2년 전

5d0d839e0e4346e4103a206494509123.png

제가 생각한 알고리즘이 어차피 가장 먼 거리가 될려면 두 단말노드 사이의 거리가 될 거고, 그러면 그 두 단말 노드의 공통조상이 root라고 할 때, 그 root에서부터 단말노드까지의 경로들 중 가장 깊이가 깊은 두개의 경로의 합이 거리가 된다고 생각하고(대신 그 두 단말노드의 최저 공통 조상은 root가 되야 하겠죠) 알고리즘을 짰는데... 왜 틀렸을까요 ㅠㅠ 혹시 단말노드 두개의 최저 공통조상이 root가 안되는건가요? 사이클이 안생겨야 되니까 그럴거같지는 않은데...

wwiiiii   2년 전

그것도 예제는 맞게 나오는데 ㅠㅠ 채점하면 틀렸다고 나와요

sujin   2년 전

7

1 2 1 3 1 -1

2 1 1 -1

3 1 1 4 3 5 2 -1

4 3 3 -1

5 3 2 6 3 7 10 -1

6 5 3 -1

7 5 10 -1

13 -> 15 (4<->7)

august14   2년 전

수진갓 차냥해!

갓수진의 말은 아마도 위 문제의 그림이 반례라는말 아닐까 싶습니다.

wwiiiii   2년 전

감사합니다! 덕분에 맞았어요 ㅠㅠ

best.first를 갱신할 때 기존의 best.first를 best.second로 갱신 안시켜줘서 틀렸었네요 ㅠ

appa   2년 전

여담으로 아무 점(v)에서 시작해서 가장 먼 점(v1)을 찾고, 그 점(v1)에서 가장 먼 점(v2)를 찾으면, v1과 v2 사이의 거리가 트리의 지름이됩니다. 다른 곳에도 응용되는 아이디어인 것 같더라구요.

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