백준 1967 - 트리의 지름 (Python)

BOJ PS/Python 2022. 12. 9. 10:56

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연

www.acmicpc.net

간만에 전적으로 아이디어부터 구현까지 혼자 한 문제...였으나 O(N)풀이법이 있더라.

내가 한 생각은 dfs를 돌되, 리프 노드까지 가면 그 점까지 가는 데 드는 최대한의 거리를 뱉는 것이었다.

그리고 이 때 자식 노드까지의 거리를 다 하나의 리스트에 저장해놓고, 자식 노드 중 가장 큰 것 두 개를 고르면 그게 부모 노드를 중심으로 한 트리의 지름이 된다. 이 때, 계산을 계속 돌면서 새로 하는 것은 낭비이다.

따라서 루트 노드인 1의 최대 거리를 구하는 과정에서 만나는 자식 노드를 가진 부모 노드의 결과를 dp라는 리스트에 저장해둔다. 그러면 결과적으로는 dfs(root node,0)만 해주면 답을 찾을 수 있다.

몇 가지 공부한 것들이 있었다.

defaultdict만이 정답이 아닐 수 있다. 오히려 defaultdict로 복잡한 연산을 하면 더 느려질 수 있다.

다만, 이 경우에는 간선이 9999개뿐이니 그럴 일은 없다.

2. 앞에서부터 n개(n>1)의 최댓값을 찾는 상황에서, 굳이 sort하지 말자. heap을 이용하는 것이 더 빠르다.

정석적인 풀이는 다음과 같았다.

이 증명을 통해 알 수 있듯, 그냥 루트 노드부터 가장 먼 노드를 찾은 후 그 노드로부터 가장 먼 노드를 찾으면 된다.

dfs 두 번이니 O(n)으로 끝낼 수 있다.

생각 생각