[백준][Python] 1595 북쪽나라의 도로 : 함수 재활용 시 반환값에 주의

트리의 지름 문제. bfs 두번을 통해 최대 거리를 두번 산출해주면 된다.

조금 중요한게 graph배열을 1부터가 아니라 0부터 만들어 주어야 한다는점.

(노드가 1개일때 내가 노드를 1로 설정해둬서.. 지금보니 그냥 target_node를 1로 설정해 주었다면 1부터 해도 될것같다)

 

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

def bfs(start):
    q = deque()
    q.append((start, 0))
    visited = [False for __ in range(10001)]
    visited[start] = True
    max_dist = 0
    target_node = 0
    while q:
        cur_node, cur_dist = q.popleft()
        for next_node, next_dist in graph[cur_node]:
            if visited[next_node]: 
                continue
            visited[next_node] = True
            dist = next_dist + cur_dist
            if dist > max_dist:
                max_dist, target_node = dist, next_node
            q.append((next_node, dist))
    return (target_node, max_dist)


edges = []
while 1:
    try:
        a, b, c = map(int, input().split())
        edges.append((a, b, c))
    except: 
        break
n = len(edges)
graph = {i: [] for i in range(10001)}
for edge in edges:
    a, b, c = edge
    graph[a].append((b, c))
    graph[b].append((a, c))
print(bfs(bfs(1)[0])[1])