백준 파이썬 1167번 트리의 지름 (Today I Learn 2025.11.02)

백준 파이썬 공부 2025.11.02
1167번 트리의 지름 (골드 2)

1. 문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 
트리의 지름을 구하는 프로그램을 작성하시오.

2. 입력
트리가 입력으로 주어진다. 
먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)
둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 
정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 
하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 
예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 
정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 
각 줄의 마지막에는 -1이 입력으로 주어진다. 
주어지는 거리는 모두 10,000 이하의 자연수이다.

3. 출력
첫째 줄에 트리의 지름을 출력한다.

4. 문제 풀이
전에 풀었던 1967번 트리의 지름과 동일한 문제인데, 간선과 가중치가 입력되는 방식만 다른 문제이다.
트리의 지름을 구하는 방식은 동일하게
아무 노드에서 가장 먼 노드 A를 구하고, A에서 가장 먼 노드 B를 찾아 A,B 사이의 거리를 구하면 된다.
가장 먼 곳의 거리를 구하는 방식은 BFS를 사용하면 된다.

>>>코드

"""
1167번 트리의 지름
입력 : n (노드의 개수)  
parent, child, w -1 (간선정보: 부모노드, 자식노드, 가중치)
출력 : diameter (트리의 지름)
>> 트리에 존재하는 모든 경로들 중 가장 긴 것의 길이
"""
from collections import deque

n = int(input())
line = [[] for _ in range(n+1)]
for i in range(n):
    data = list(map(int, input().split()))
    parent = data[0]
    idx = 1
    while data[idx] != -1:
        child, w = data[idx], data[idx+1]
        line[parent].append((child, w))
        idx += 2

def tree_dist(start):
    queue = deque()
    queue.append(start)
    
    dist = [-1] * (n+1)
    dist[start] = 0
    while queue:
        cur = queue.popleft()
        
        for next_node, w in line[cur]:
            if dist[next_node] == -1:
                dist[next_node] = dist[cur] + w
                queue.append(next_node)
    
    far_node = dist.index(max(dist))
    return far_node, max(dist)

a, _ = tree_dist(1)
_, diameter = tree_dist(a)
print(diameter)

5. 문제 링크
https://www.acmicpc.net/problem/1167