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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


n = int(input().strip())
graph = [[] for _ in range(n+1)]


def dfs(u, wt):
    for x in graph[u]:
        v = x[0]
        v_wt = x[1]

        if dist[v] == -1:
            dist[v] = wt + v_wt
            dfs(v, dist[v])


for _ in range(n-1):
    u, v, wt = map(int, input().split())
    graph[u].append((v, wt))
    graph[v].append((u, wt))

# 임의의 노드에서 가장 먼 곳 x를 찾고, 그 x에서 가장 먼 곳 y를 찾는다.
# x ~ y의 거리가 트리의 지름이 된다.
dist = [-1]*(n+1)

# 노드 1에서 가장 먼 노드를 찾는다
dist[1] = 0
dfs(1, 0)

# 노드 1에서 가장 먼 노드 furthest에서 가장 먼 노드를 찾는다
furthest = dist.index(max(dist))
dist = [-1]*(n+1)
dist[furthest] = 0
dfs(furthest, 0)

# furthest ~ 가장 먼 노드까지의 거리가 지름이 된다
# 출력
print(max(dist))

---

🧂아이디어

탐색, 그래프이론

참고: https://kyun2da.github.io/2021/05/04/tree's_diameter/

• 트리의 지름: 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이

• 임의의 노드에서 가장 먼 노드 x를 찾고, 그 x에서 가장 먼 노드 y를 찾는다.

• 임의의 노드에서 가장 먼 노드 x를 찾는 이유

  • 지름을 구성하는 두 파란색 노드들은 그 사이에 있는 다른 회색 노드들에서 가장 먼 노드들이다.
    (회색 노드의 위치에 따라 왼쪽 파란 노드가 가장 먼 노드가 될 수도, 오른쪽 파란 노드가 가장 먼 노드가 될 수도 있음)
  • 따라서, 임의의 노드에서 찾은 가장 먼 노드 x는 지름을 구성하는 두 파란색 노드들 중 하나이고, 그 x에서 가장 먼 노드 y는 또다른 파란색 노드가 된다.

• x에서 y까지의 길이가 트리의 지름이 된다.

유사한 문제: [백준 1167] 트리의 지름