Leetcode 310. Minimum Height Trees

https://leetcode.com/problems/minimum-height-trees/

Minimum Height Trees - LeetCode

 

---

문제를 보고 바로 전에 풀었던 Course schedule topological sort 문제가 생각났는데요

2022.09.23 - [‼ ERROR RECORD] - Leetcode 207. Course Schedule 풀이 (Topological Sorting, BFS, DFS)

Leetcode 207. Course Schedule 풀이 (Topological Sorting, BFS, DFS)

다만, 여기서 차이점은 연결의 순서가 중요하지 않다는 점이었습니다.

처음 접근은 당연히 가장 연결 노드가 많은 노드가 root가 되면 최소 높이의 그래프를 반환한다고 생각했지만 

막상 해보니 이 접근은 자식노드가 우측이나 왼쪽 노드가 비정상적으로 긴 경우 같은 예외를 포함하지 못했습니다 ㅠ

 

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        
#         indegree, neighbor = defaultdict(int), defaultdict(list)
        
#         for e in edges:
#             indegree[e[0]] += 1
#             indegree[e[1]] += 1
#             neighbor[e[1]].append(e[0])
#             neighbor[e[0]].append(e[1])

#         start, visit = [i for i in range(n) if indegree[i] == max(indegree.values())], set()
        
#         while start:
#             node = start.pop()
#             if node not in visit:
#                 visit.add(node)
#                 for neigh in neighbor[node]:
#                     indegree[neigh] -= 1
#                     if indegree[neigh] > 0:
#                         start.append(neigh)
#         return visit

그래서 이 코드는 계속 wrong answer을 반환하더라구요

 

---

모범 풀이 예시)

 

대부분의 풀이에서 접근은 간단했습니다. 단 하나의 노드만 연결된 노드의 연결선을 없애다 보면 가장 마지막에 남는

노드가 바로 우리가 찾는 root노드라는 점이었습니다.

 

풀이 1)

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(set)
        
        for e in edges:
            adj[e[0]].add(e[1])
            adj[e[1]].add(e[0])
            
        leave_nodes = [node for node in adj if len(adj[node])==1]
        total = n
        
        if total ==1:
            return [0]
        
        while total > 2:
            total -= len(leave_nodes)
            next = []
            for leaf in leave_nodes:
                neighbor = adj[leaf].pop()
                adj[neighbor].remove(leaf)
                if len(adj[neighbor]) == 1:
                    next.append(neighbor)
            leave_nodes = next
        return leave_nodes

전체 노드의 수가 하나가 남을 때까지 while 문을 돌리고 노드가 하나 연결된 leave_node 를 뽑아서

adj[neighbor].remove(leaf)를 통해 leave_node가 연결되었던 노드에서 leaf의 연결을 끊어냅니다.

 

이렇게 연결선을 없애면 또 다시 연결선이 하나인 노드가 생성되겠죠?

그걸 여기 if 문에서 담아주고 새로 작업해야 하는 leave_node로 append 해줍니다

 

 

---

풀이 2)

def findMinHeightTrees(n, edges):
	tree = [set() for _ in range(n)]
	for u, v in edges: tree[u].add(v), tree[v].add(u)
	q, nq = [x for x in range(n) if len(tree[x]) < 2], []
	while True:
		for x in q:
			for y in tree[x]:
				tree[y].remove(x)
				if len(tree[y]) == 1: nq.append(y)
		if not nq: break
		nq, q = [], nq
	return q

전체적인 논리는 같지만 좀 더 명료하게 정리된 코드입니다.

tree = [set() for _ in range(n)]은 defaultdict(set)으로 대체 가능할 것 같습니다.

여기서 차이점은 while 문에서 전체 total의 개수가 1개일 때로 가정한게 아니라 while true를 지정하고

if not nq 즉, nq가 빈 리스트가 아닐 때, nq를 다시 초기화하고 for 문에 들어가는 q를 nq로 지정했습니다.

 

---

이 문제를 풀면서 느낀 점은 하나의 규칙이 예시답안에 맞다고 해서 무조건적으로 따를게 아니라,

다양한 예외 경우를 상상해보면서 답을 찾을 수 있는 합리적인 규칙을 찾고 코딩으로 옮겨야 한다는 점입니다 

 

성급하게 결론으로 가기 보다는 생각하는 법을 더 연습해야겠습니다