49. Minimum Height Trees

🎯 leetcode - 310. Minimum Height Trees

---

📌 문제

- 파이썬 알고리즘 인터뷰 49번 문제

📌 날짜

2020.02.18

📌 시도 횟수

4 try / Failed

💡 Code

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 1:
            return [0]
            
        # 양방향 그래프 생성    
        graph = defaultdict(list)
        for i, j in edges:
            graph[i].append(j)
            graph[j].append(i)
            
        # leaves에 리프 노드들을 모두 담는다.
        leaves = []
        for i in range(n + 1):
            if len(graph[i]) == 1:
                leaves.append(i)

        while n > 2:  # 마지막에 남을 수 있는 노드는 1개 또는 2개이다.
            n -= len(leaves)
            new_leaves = []
            for leaf in leaves:
                # 리프 노드를 삭제한다.
                neighbor = graph[leaf].pop()  # 먼저 리프 노드를 key로 갖는 딕셔너리를 삭제하고
                graph[neighbor].remove(leaf)  # 리프노드를 value로 갖는 인접 노드들에 대해서도 삭제

                # 삭제한 후, 다시 삭제한 그래프의 리프 노드를 담는다.
                if len(graph[neighbor]) == 1:  # 리프노드의 인접 노드만 검사하면 된다.
                    new_leaves.append(neighbor)

            leaves = new_leaves
        return leaves

💡 문제 해결 방법

- "단계별 리프 노드 제거" 방법을 이용하면 풀 수 있다.
- 마지막에 남을 수 있는 최종 노드는 1개 또는 2개이다.
따라서 노드가 2개 이하로 남을때까지 리프 노드를 제거한다.

1. 제거할 리프노드를 leaves에 담는다.
리프 노드일 경우 graph에서 value의 요소가 1개 뿐이다.
2. 마지막 남을 수 있는 노드가 2개 이하가 될 때 까지...
3. 리프 노드를 삭제하고
4. 리프 노드와 인접한 노드에 대해 value가 1개인 리프노드를 new_leaves에 담는다.
5. leaves = new_leaves를 해준 뒤, 다시 위의 과정을 반복한다.


🎀 리프 노드 삭제하는 법
- 위의 graph는 양방향이기 때문에 리프 노드는 딕셔너리의 key, value 두 군데에 모두 있다.
- 먼저 리프노드를 key값으로 가지는 딕셔너리를 삭제한다.
- 이후, 리프노드를 value로 가지는 딕셔너리에 대하여 해당 리프노드를 value에서 제거한다.

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 모든 노드에 대해 해당 노드를 루트로 설정했을 때의 깊이를 다~ 계산한 뒤,
가장 작은 깊이를 가진 노드들을 다시 리스트에 담아서 리턴했더니...
- 시간 초과 됐다.

---