백준 1167 트리의 지름 풀이 ( 파이썬 )
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지
www.acmicpc.net
입력 형식만 다르지 1967번(yanoo.tistory.com/53) 과 같은 풀이.
import sys
input=sys.stdin.readline
n=int(input())
tree=[[] for _ in range(n+1)]
result1=[0 for _ in range(n+1)]
result2=[0 for _ in range(n+1)]
def dfs(cur,result):
for i in range(len(tree[cur])):
end,dis=tree[cur][i]
if result[end] == 0:
result[end]=result[cur]+dis
dfs(end,result)
for i in range(n):
arr=list(map(int,input().split()))
start=arr[0]
leng=len(arr)
for i in range(1,leng,2):
if arr[i]==-1:
break
else:
tree[start].append((arr[i],arr[i+1]))
dfs(1,result1)
result1[1]=0
maxi=0
index=0
for i in range(len(result1)):
if maxi<result1[i]:
maxi=result1[i]
index=i
dfs(index,result2)
result2[index]=0
print(max(result2))
[ baekjoon ] 탈출 3055번 ( python ) (0) | 2021.05.24 |
---|---|
[ baekjoon ] 문자열 복사 2195번 ( python ) (0) | 2021.05.15 |
[ baekjoon ] 트리의 지름 1967번 ( python ) (0) | 2021.05.08 |
[ baekjoon ] 트리의 부모 찾기 11725번 ( python ) (0) | 2021.05.07 |
[ baekjoon ] 두 배열의 합 2143번 ( python ) (0) | 2021.04.27 |