[Python] 백준 1167, 1967

 

입력값의 차이 외에는 똑같은 문제이다.

 

 

 

 

먼저 트리의 지름을 찾는데에는 rule이 있다.

✔ 트리에서 임의의 노드(A)를 선택해 가장 먼 노드를 찾는다. -> B

✔ B에서 가장 먼 노드를 찾는다. -> C

✔ 그러면 B와 C사이의 거리가 가장 멀다. (==지름)

이 규칙을 알면 쉽게 쉽게 풀 수 있겠다. 모르면 ㅠㅠ 삽질 하니까 알고있자...

 

 

Answer 1167

import sys
from collections import defaultdict
from collections import deque

n=int(sys.stdin.readline())
dic=defaultdict(list)

for i in range(n):
	l=list(map(int,sys.stdin.readline().split()))
	a=l[0]
	l=l[1:]
	for i in range(1,len(l),2):
		dic[a].append([l[i-1],l[i]])

#임의의 노드에서 가장 먼 노드를 찾는 부분 (나는 1을 임의의 점으로 두었음)
visited=[0 for x in range(n+1)]
#방문했음을 표시하기 위해 1을 넣어줌
visited[1]=1
q=deque([[1,0]])
while q:
	m,cnt=q.popleft()
	for x,y in dic[m]:
		if visited[x] == 0:
			q.append([x,cnt+y])
			visited[x]=cnt+y
            
#반례로 최댓값이 1이 되었을 때 a가1이 되는 경우를 막기 위해 0으로 돌려놓음
visited[1]=0
a=1
for i in range(n+1):
	if visited[i]>visited[a]:
		a=i

#트리의 지름을 찾는 부분
visited=[0 for x in range(n+1)]
visited[a]=1
q=deque([[a,0]])
while q:
	m,cnt=q.popleft()
	for x,y in dic[m]:
		if visited[x] == 0:
			q.append([x,cnt+y])
			visited[x]=cnt+y
visited[a]=0
print(max(visited))

 

Answer 1967

import sys
from collections import defaultdict
from collections import deque

n=int(sys.stdin.readline())
dic=defaultdict(list)

for i in range(n-1):
	a,b,c=map(int,sys.stdin.readline().split())
	dic[a].append([b,c])
	dic[b].append([a,c])

visited=[0 for x in range(n+1)]
visited[1]=1
q=deque([[1,0]])
while q:
	m,cnt=q.popleft()
	for x,y in dic[m]:
		if visited[x] == 0:
			q.append([x,cnt+y])
			visited[x]=cnt+y
visited[1]=0
a=1
for i in range(n+1):
	if visited[i]>visited[a]:
		a=i

visited=[0 for x in range(n+1)]
visited[a]=1
q=deque([[a,0]])
while q:
	m,cnt=q.popleft()
	for x,y in dic[m]:
		if visited[x] == 0:
			q.append([x,cnt+y])
			visited[x]=cnt+y
visited[a]=0
print(max(visited))