https://leetcode.com/problems/find-minimum-diameter-after-merging-two-trees
트리의 지름을 구하는 문제였습니다.
📕 풀이방법
📔 입력 및 초기화
인접리스트 graph1, graph2를 구해줍니다.
📔 풀이과정
* 트리의 지름은 bfs를 두 번 수행해 구할 수 있습니다.* n개의 노드에 대해 n-1개의 간선이 보장되므로 노드번호 띄엄띄엄 포함된 간선이 입력으로 들어오는 경우가 없습니다.1. 첫 번째 bfs로 끝 노드를 구한 뒤 해당 노드를 시작점으로 두 번째 bfs를 수행한다면 트리의 지름이 나옵니다.
2. 해당 부분을 bfs_diameter라는 함수를 선언해 bfs를 두 번 수행한 결과로 구한 지름 diameter를 구하고 반환합니다.
3. 트리를 잇게 된다면 최소 트리 지름은 각 트리의 중심점끼리 잇는 방법 뿐입니다.
📔 정답출력
홀수 지름을 가진 트리가 있다면 1을 더해 짝수로 만들고 2로 나눠 가장 근접한 트리의 반지름을 구해 서로 더한 값에서 중심사이 연결점 끼리 이어저 길어진 1을 더해줍니다.
edges2가 단일 노드인 경우, edges1가 단일 노드인 경우, (각 트리의 지름+1) // 2 + 1의 최댓값을 반환합니다.
📕 Code
📔 Python3
from collections import deque, defaultdict
class Solution:
def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
def build_graph(edges):
graph = defaultdict(list)
for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
return graph
def bfs_diameter(graph):
def bfs(start):
dq = deque([(start,0)])
visited = {}
visited[start] = True
furthest_node, max_dist = start, 0
while dq:
node, dist = dq.popleft()
for next in graph[node]:
if visited.get(next):
continue
visited[next] = True
if dist + 1 > max_dist:
furthest_node, max_dist = next, dist + 1
dq.append((next, dist + 1))
return furthest_node, max_dist
furthest_node, _ = bfs(0)
_, diameter = bfs(furthest_node)
return diameter
graph1 = build_graph(edges1)
graph2 = build_graph(edges2)
diameter1 = bfs_diameter(graph1)
diameter2 = bfs_diameter(graph2)
return max((diameter1), (diameter2), (diameter1 + 1) // 2 + (diameter2 + 1) // 2 + 1)📕 Test Case
몇 가지 반례를 직접 작성해 보았습니다.
input
edges1 = [0,1]
edges2 = []
답
2
input
edges1 = []
edges2 = []
답
1
input
edges1 = [[0, 1], [1, 2]]
edges2 = [[0, 1], [1, 2], [2, 3]]
답
5
*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.