1167 트리의 지름순

1.접근

모든 정점을 기준으로 DFS를 들어가보는 생각밖에 나지 않아서 풀어봤지만 시간초과가 났다(2≤V≤100,000)

도저히 생각나지 않았는데 트리의 지름을 구하는 쉬운 방법이 있었다.

2.풀이

트리의 지름을 구하려면 임의의 점을 잡고 그 점으로부터 최대거리를 가진 곳의 인덱스에서 다시 최대 거리를 구하면

그것이 지름이 된다.(처음 임의의 점에서 최대거리를 구할 때 트리의 지름과 겹치는 부분이 생길 수 밖에 없기 때문에 이라고 한다.) 따라서 DFS를 두번 써주면 된다 (임의의 점,임의의 점에서의 최대 거리 인덱스)

트리의 지름을 구하는 공식은 이곳에 자세히 있다.https://blog.myungwoo.kr/112

3.코드

	import sys
	input=sys.stdin.readline
	sys.setrecursionlimit(10**9)
	n=int(input())
	adj=[[]for _ in range(n+1)]
	#입력받음
	for i in range(n):
	L=list(map(int,input().split()))
	for j in range(len(L[1:])):
	if j%2==1:
	adj[L[0]].append((L[j],L[j+1]))
	#dfs 들어가서 배열에 도착하는 곳까지의 거리 저장
	def dfs(v,result):
	for a, b in adj[v]:
	if result[a] == -1:
	result[a]=result[v]+b
	dfs(a,result)
	#임의의 점에서 최대 거리 저장
	result1=[-1]*(n+1)
	result1[1]=0
	dfs(1,result1)
	temp=0
	index=0
	#최대값일때의 인덱스값을 찾음
	for i in range(1,len(result1)):
	if result1[i]>temp:
	temp=result1[i]
	index=i
	#그 인덱스에서 시작하는 최대값 찾음
	result2=[-1]*(n+1)
	result2[index]=0
	dfs(index,result2)
	print(max(result2))

view raw 1167트리의 지름.py hosted with ❤ by GitHub

4.배운점

• DFS나 재귀를 쓸때는 습관적으로 sys.setrecursion을 해주어야겠다 (런타임에러 방지)
• 트리의 지름 구하는 공식은 알아두자
• 입력 받을 때 순서대로 올꺼라고 생각하지말자(하루날림)