오답 여부: o
편집 시간: 2022년 2월 24일 오후 2:58
코드
Algorithm/1967.py at main · Junroot/Algorithm
풀이
잘못된 풀이
처음에는 분할 정복으로 문제를 접근했다. 현재 루트 노드x에서 자식 노드를 두개 선택해서 두 깊이의 합을 f(x)라고 했을 때, x의 자식 노드들 a,b에 대해서 f(a), f(b)가 있을 때 max( f(x), f(a), f(b) ) 답이라고 생각했지만 수많은 재귀와 연산과정으로 메모리 초과 또는 시간초과가 발생했다.
맞는 풀이
트리에서 지름을 구하는 방법이 따로 있었다. 임의의 노드에서 트리 안에 가장 먼 노드를 a라고 했을 때, a와 가장 먼 노드 사이의 거리가 지름에 해당한다.