[백준][Python] 1967번 트리의 지름

1967번: 트리의 지름

 

 

코드

import sys
from collections import deque
def dfs(a,l):
	queue = deque()
	queue.append((a,l))
	while queue:
		a,l = queue.popleft()
		for na,nl in graph[a]:
			if distance[na] == -1:
				queue.append((na,nl))
				distance[na] = distance[a]+nl
	return distance.index(max(distance))  # a번 노드와 가장 멀리 떨어진 노드 번호 return

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
	a,b,l = map(int,sys.stdin.readline().split())
	graph[a].append([b,l])
	graph[b].append([a,l])
distance = [-1]*(n+1)
distance[1] = 0
num = dfs(1,0)
distance = [-1]*(n+1)
distance[num] = 0
print(distance[dfs(num,0)])

 

설명

가장 긴 길이를 구하는 방법을 모르겠어서 검색을 해봤다.

- 먼저 dfs를 이용하여 1번 노드에서 가장 먼 노드 번호 num을 구한다.

- 다시 dfs를 이용하여 num번 노드에서 가장 먼 노드까지의 거리를 구하면 그 값이 트리의 지름이다.