-
트리 트리오 중간값코딩 테스트/Level 4 2022. 12. 11. 18:42반응형
https://school.programmers.co.kr/learn/courses/30/lessons/68937
def solution(n, edges): def bfs(first_node): queue = deque([(first_node, 0)]) visited = {first_node: 0} max_dist = 0 while queue: node, distance = queue.popleft() for next_node in tree[node]: if next_node not in visited: visited[next_node] = distance + 1 queue.append((next_node, distance + 1)) max_dist = max(max_dist, distance + 1) return max_dist, [k for k, v in visited.items() if v == max_dist] def solve(): _, some = bfs(1) max_dist, others = bfs(some[0]) if len(others) >= 2: return max_dist else: max_dist, others = bfs(others[0]) if len(others) >= 2: return max_dist else: return max_dist - 1 from collections import defaultdict, deque tree = defaultdict(list) for a, b in edges: tree[a].append(b) tree[b].append(a) return solve() print(solution(4, [[1, 2], [2, 3], [3, 4]])) print(solution(5, [[1, 5], [2, 5], [3, 5], [4, 5]]))
반응형