트리

[python3] 1167 풀이 (트리의 지름, 트리, DFS)

문제가 어려워서 힌트를 봤고 이해하고 나니 쉽게 풀 수 있었다. 트리가 주어진다. 이때 트리의 지름을 구하는 문제이다. 트리의 지름을 어떻게 구해야하는지 이해하지 못하면 풀수가 없다. 트리가 주어졌을대 트리의 지름을 구하기 위해서는 가장 끝점을 알아내야한다. 처음에는 각 노드마다 다익스트라를 할지 플로이드를 할지 고민했다. 그런데 주어지는 노드가 100,000개이기 때문에 구할 수가 없다. 따라서 다른 방법을 사용해야한다. 그래서 이리저리 지지고 볶으니 한줄로 세우는 방법이면 되지 않을까 싶었다. 그래서 한줄로 세워보았다. 그런데 이렇게 세운다고 달라지지가 않았다. 더이상 고민하는게 무의미하여 찾아보니 아무 노드나 잡고 가장 먼것을 찾아본다. 그럼 지름의 끝 노드를 찾을 수 있었다. 만약 3번 노드에서 ..