[백준] 1967번 : 트리의 지름

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

해당 문제는 깊이 우선탐색으로 문제를 해결 하였습니다.

 

1. 아무노드로 부터 시작하여 깊이우선탐색을 하여 가장 긴 노드를 찾습니다.

2. 가장 긴 노드로부터 다시 깊이우선탐색을하여 다른 노드까지의 긴 길이를 찾습니다.

 

가장 긴 길이가 트리 의 지름입니다.

이유 : 트리는 사이클이 없어서, 한 노드로부터 다른 한노드까지의 경로는 단 하나 존재합니다.

따라서 아무 노드로부터 시작하여 끝점을 구한뒤 그 끝점에서부터 다른 하나의 끝점 까지의 거리를 구하면 트리의 길이가 됩니다.

 

따라서 깊이우선탐색을 2번 해주면 원하는 결과를 얻을 수 있습니다. 임의의 한점을 루트로 잡았습니다.

import sys
sys.setrecursionlimit(10001)

n = int(input())

graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

def dfs(node, cost):
    global max_distance, farthest_node
    visited[node] = True
    if cost > max_distance:
        max_distance = cost
        farthest_node = node
    for v1, distance in graph[node]:
        if not visited[v1]:
            dfs(v1, cost + distance)

max_distance = -1
farthest_node = 0
visited = [False for _ in range(n+1)]
dfs(1, 0)  # 첫 번째 DFS

visited = [False for _ in range(n+1)]
max_distance = -1
dfs(farthest_node, 0)  # 두 번째 DFS

print(max_distance)