https://leetcode.com/problems/minimum-height-trees/
트리 문제로 처음에는 모든 노드를 dfs 로 탐색하며 가장 height 가 낮은 label 을 관리하는식으로 접근했습니다.
당연히 Time out 이 발생했고요.. O( N * (N+ E) )
다른 방법이 떠오르지 않아 알고리즘 트레이닝 책에 소개된 Tree 알고리즘 편을 참고해서 구현했습니다.
핵심은 트리의 지름을 구하고 지름의 중간에 위치한 Node 가 MHTs’ root labels 입니다.
( 지름의 중간이 2로 나누는 개념이기 때문에 지름의 길이가 짝수면 MHTs’ root labels은 1개 , 홀수면 2개 )
그럼 트리의 지름을 구하는 방법부터 알아봐야합니다.
책에서 지름을 구하는 2가지 방법을 소개하지만 저는 간단하면서 아름다운 방법인 2번째 방법으로 접근하겠습니다.
- 랜덤의 노드(a)에서 시작해서 a 에서 가장 먼 노드(b)를 탐색합니다.
- 위에서 찾은 b 에서 탐색을 시작해서 다시 가장 먼 노드(c)를 탐색합니다.
- b 와 c의 거리가 트리의 지름입니다.
이렇게 BFS 혹은 DFS 2번 탐색하면 트리의 지름을 구할 수 있습니다.
책에서는 트리의 지름을 이루는 경로가 수평으로 위치하고 다른 노드가 매달린 형태로 트리가 다시 그려지기 때문에 노드 b 를 지름의 한 끝으로 삼는것는 항상 올바른 선택이 된다고 합니다.
( 이 알고리즘이 왜 동작하는지는 다양한 블로그에서 더 자세하게 혹은 복잡하게 설명하고 있습니다 )
실제로 이 책에서는 이 알고리즘이 아주 아름답다고 표현하는데 기억하기 간단하기 때문에 트리의 지름 구하는 방법은 이 방법으로 기억하려고 합니다.
다시 310번 문제로 돌아가보겠습니다.
지름의 중간이 MHTs’ root labels 이기 때문에 문제를 2가지로 접근해볼 수 있습니다.
- 지름을 구하고 지름에 해당하는 경로를 찾아 경로의 중간 값을 반환한다.
- 지름에 해당하는 양 끝 노드를 기준으로 양끝 노드간의 거리를 구해서 최소가 되는 노드를 반환한다.
저는 2번이 이해하기 좀 더 간단하기 때문에 2번으로 문제를 풀어보았습니다.
지름의 양끝에서 각 노드간의 거리를 dp 로 구해하기 위해 총 DFS 를 3번 탐색했습니다.
그리고 각 node 에서 지름의 양쪽 끝까지의 거리 중 max 값을 계산하여 각 node 가 root 가 되었을때의 tree height( 지름의 양끝까지 중 가장 먼 거리) 를 확인합니다.
이번 문제는 트리의 기본적인 탐색 뿐만 아니라 트리의 주요 특성을 충분히 이해할때 풀 수 있는 문제인것 같습니다.
트리의 지름 구하기 뿐만 아니라 트리의 서브트리 질의/ 경로 질의 같은 추가적인 트리 기본 기술들을 학습 해야겠습니다.
물론 가장 기본 되는 트리의 용어나 탐색 방법에 대해서도 기억해야합니다. (아래는 이전 그래프 관련 문제)
제출 코드 : https://github.com/sok891111/leetcode/blob/main/310.%20Minimum%20Height%20Trees.py
제가 제출한 코드는 DFS 를 3번 탐색하기 때문에 속도가 빠르지는 않습니다.
chatGPT 에게 이번 문제를 물어봤을때 O(n) 시간복잡도를 가진 알고리즘을 알려주네요.
접근법 자체는 지름의 중심은 1개 혹은 2개 여서 트리의 leaf( 트리의 차수가 1, 즉 자식 노드가 없는 노드 )를 노드가 2개 이하 남을때까지 잘라 나가다 보면 트리의 중심( 지름의 중간) 에 도착한다는 접근법 입니다.
트리를 가장자리부터 계속 잘라 나가다보면 중심에 도착할 수 있다는 접근법이네요. ( 아름다운 알고리즘입니다.)
마지막으로 python 에서 일반 array 보다 큐의 insert, delete 에서 deque 가 더 빠르다고 합니다.
가능하면 deque 를 사용하는 습관을 가져보려고 합니다. 또한 DFS 구현시 visited 변수는 set 으로 구현하는게 훨씬 빠릅니다.
참고 : https://www.weeklyps.com/entry/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84#d2
알고리즘 트레이닝 책.