[백준 1967] 트리의 지름 ❗
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))
🧂아이디어
탐색, 그래프이론
-
트리의 지름: 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이
-
임의의 노드에서 가장 먼 노드 x를 찾고, 그 x에서 가장 먼 노드 y를 찾는다.
-
임의의 노드에서 가장 먼 노드 x를 찾는 이유
- 지름을 구성하는 두 파란색 노드들은 그 사이에 있는 다른 회색 노드들에서 가장 먼 노드들이다.
(회색 노드의 위치에 따라 왼쪽 파란 노드가 가장 먼 노드가 될 수도, 오른쪽 파란 노드가 가장 먼 노드가 될 수도 있음)
- 따라서, 임의의 노드에서 찾은 가장 먼 노드 x는 지름을 구성하는 두 파란색 노드들 중 하나이고, 그 x에서 가장 먼 노드 y는 또다른 파란색 노드가 된다.
-
x에서 y까지의 길이가 트리의 지름이 된다.
유사한 문제: [백준 1167] 트리의 지름
Author And Source
이 문제에 관하여([백준 1967] 트리의 지름 ❗), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@eastgloss0330/백준-1967-트리의-지름
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
트리의 지름: 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이
임의의 노드에서 가장 먼 노드 x를 찾고, 그 x에서 가장 먼 노드 y를 찾는다.
임의의 노드에서 가장 먼 노드 x를 찾는 이유
- 지름을 구성하는 두 파란색 노드들은 그 사이에 있는 다른 회색 노드들에서 가장 먼 노드들이다.
(회색 노드의 위치에 따라 왼쪽 파란 노드가 가장 먼 노드가 될 수도, 오른쪽 파란 노드가 가장 먼 노드가 될 수도 있음) - 따라서, 임의의 노드에서 찾은 가장 먼 노드 x는 지름을 구성하는 두 파란색 노드들 중 하나이고, 그 x에서 가장 먼 노드 y는 또다른 파란색 노드가 된다.
x에서 y까지의 길이가 트리의 지름이 된다.
유사한 문제: [백준 1167] 트리의 지름
Author And Source
이 문제에 관하여([백준 1967] 트리의 지름 ❗), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@eastgloss0330/백준-1967-트리의-지름저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)