1967번 트리의 지름 풀이

문제 링크: https://www.acmicpc.net/problem/1967

백준 알고리즘 기초 2/2 620에서 5번째 - 1967번 트리의 지름을 풀어보았다.

 

풀이: https://kyun2da.github.io/2021/05/04/tree's_diameter/ 를 참고했다.

 

C++

 

Python

import sys
sys.setrecursionlimit(10**9)

def dfs(st,p):
	for i in tree[st]:
		a,b=i
		if dis[a]==-1:
			dis[a]=p+b
			dfs(a,p+b)

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	tree[a].append([b,c])
	tree[b].append([a,c])
dis=[-1]*(n+1)
dis[1]=0
dfs(1,0)
ldis=dis.index(max(dis))
dis=[-1]*(n+1)
dis[ldis]=0
dfs(ldis,0)
print(max(dis))

Java