[자바] 백준 1167 - 트리의 지름

지름이 뭘 이야기하는지 정확히 이해 못하고 너무 쉽게 생각했다.

루트 노드(1)에서 가장 멀리 있으면서 거리가 가장 먼 노드 사이의 모든 거리를 더하면 된다고 생각했는데, 

아래 블로그 글 보고, 꼭 그런 경우만 있지는 않다는 걸 깨달았다. 

 

mygumi.tistory.com/226

백준 1967번 트리의 지름 :: 마이구미

근데 위 블로그 내용 중에서 

 

"가장 길게 늘어나는 경우인 두 노드를 찾는 것이 문제의 핵심이다.

쉽게 알 수 있는 것은 두 노드는 가장 아래에 있는 노드가 될 것이다.

그렇기에, 가장 깊이 있는 노드를 찾아야하기에 DFS가 적합하게 된다."

라는 내용이 있는데, 어떻게 보면 당연한 말인데 이런 당연해 보이는 아이디어를 발전시켜나가는 부분이 어렵다. 

알고리즘을 생각하면서 '당연하다'고 생각했던 부분을 다시 한번 되짚어보고 정말 당연한지 고민해보는 연습은 많이 하는데, 이게 점점 어디까지가 당연하고 어디까지가 당연하지 않은지 경계가 없어지는 것 같다. 

 

+ 다른데서 찾아보니 트리의 지름을 구하는 일종의 공식이 있다. 

1. 임의의 노드 X에서 가장 먼 노드 A를 찾는다.

2. 노드 A에서 가장 먼 노드 B를 찾는다.

3. 트리의 지름은 노드 A와 노드 B 사이의 거리이다. 

 

여러 가지 경우의 수를 생각해봤는데, 맞는 말인 것 같은데 완전한 증명은 못하겠어서 좀 답답하다. 

이 문제에서는 노드 1에서 가장 먼 노드를 찾은 뒤에, 그 노드를 시작점으로 하여 또 가장 먼 노드를 찾는 방식으로 해야겠다.