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

💻 문제 - G2

👉 제출 코드

import sys
input = sys.stdin.readline
from collections import deque

# 1
V = int(input())
graph = [[] for _ in range(V+1)]
for _ in range(V):
    c = list(map(int, input().split()))
    for e in range(1, len(c)-2, 2):
        graph[c[0]].append((c[e], c[e+1]))
    
def bfs(start):
    visited = [-1] * (V+1)
    q = deque()
    q.append(start)
    visited[start] = 0
    _max = [0, 0] 
    
    while q:
        x = q.popleft()
        for e, w in graph[x]:
            if visited[e] == -1:
                visited[e] = visited[x] + w
                q.append(e)
                if _max[0] < visited[e]:
                    _max = visited[e], e
    return _max

# 2
dis, node = bfs(1)
dis, node = bfs(node)
print(dis)

#1. graph에 튜플로 저장한다.
#2. 그래프에서 가장 멀리 떨어져 있는 두 노드는 임의의 한 노드에서 가장 떨어진 노드 중 하나이다. ➡️ 1에서 가장 먼 노드를 구하여 나온 노드를 저장하고, 그 노드를 탐색하여 가장 길이가 길게 나온 케이스를 출력한다.