[CLASS 4]백준 1167번 - 트리의 지름

1167번 : 트리의 지름

 

트리의 지름의 특징에 대해 잘 생각해보면 DFS를 통해 쉽게 풀 수 있는 문제이다.

 

해당 문제랑 완전히 동일한 문제를 풀었었다... https://dawitblog.tistory.com/153 왠지 너무 익숙하더라..

 

[CLASS 4]백준 1967번 - 트리의 지름

 

내 코드:

# dawitblog.tistory.com/168
from sys import stdin
input = stdin.readline

# 입력
n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n):
    info = list(map(int,input().split()))
    a = info[0] - 1
    for i in range(1,len(info)-1,2):
        b = info[i] - 1
        c = info[i+1]

        tree[a].append((b,c))

# 거리를 담을 리스트
sum_list = []
# DFS
def dfs(now,prev,cost_list):
    # 잎새 노드이면서 시작점이 아닐때
    if len(tree[now]) == 1 and prev != -1:
        sum_list.append((sum(cost_list),now))
        return
    
    for next,cost in tree[now]:
        if next != prev:
            cost_list.append(cost)
            dfs(next,now,cost_list)
            cost_list.pop()

dfs(0,-1,[])
# 지름의 한 끝점(노드)
start = max(sum_list)[1]
sum_list = []
# 지름의 한 끝점에서 가장 먼 점(노드)까지의 거리
dfs(start,-1,[])
print(max(sum_list)[0])