[백준] [DFS] [트리] 1967. 트리의 지름

1967. 트리의 지름

1967번: 트리의 지름

 

• 내 풀이
  • 트리를 dfs로 돌때 루트 노드를 설정하면 됨
    • 그 루트를 기준으로 거리 계산
    • 처음 1을 루트로 거리 계산 한 후에 가장 큰값을 찾아서
    • 그 큰 값에서 거리가 가장 긴 값을 찾으면됨 -> 두 노드를 끝점으로하는 최장 거리
  • 트리 간선 정보를 단방향만 입력해주니까 양방향으로 넣어주기

import sys
sys.setrecursionlimit(10**6)

def dfs(i):
    for gp in graph[i]:
        c,v=gp
        if visited[c]==-1:
            visited[c]=visited[i]+v
            dfs(c)
  
n=int(input())
graph=[[] for _ in range(n+1)]
for _ in range(n-1):
    p,c,v=map(int,input().split())
    graph[p].append([c,v])
    graph[c].append([p,v])

visited=[-1 for _ in range(n+1)]
visited[1]=0

dfs(1)

maxIdx=visited.index(max(visited))
visited=[-1 for _ in range(n+1)]
visited[maxIdx]=0

dfs(maxIdx)

print(max(visited))