[백준(파이썬/Python)] 1967_트리의 지름

 

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

1967번: 트리의 지름

 

백준 1167번 트리의 지름 문제와 완벽하게 동일해서 해당 문제에 대한 풀이를 참고하면 될 것 같습니다.

[백준(파이썬/Python)] 1167_트리의 지름

 

 

from collections import defaultdict, deque
import sys

def bfs(start):
    node, diameter = 0, 0

    visited = [False] * (n+1)
    visited[start] = True
    q = deque()
    q.append((start, 0))    

    while q:
        now, cost = q.popleft()

        if diameter < cost:
            diameter = cost
            node = now

        for t in tree[now]:
            child, weight = t[0], t[1]
            if not visited[child]:
                q.append((child, cost + weight))
                visited[child] = True
    return node, diameter



n = int(input())
tree = defaultdict(list)

# 트리 초기화
for _ in range(n-1):
    a, b, weight = map(int, sys.stdin.readline().split())
    tree[a].append((b, weight))
    tree[b].append((a, weight))
    

randomNode, maxDist = bfs(1)
randomNode, maxDist = bfs(randomNode)
print(maxDist)