[백준] 1595번 북쪽나라의 도로 (Python)

백준 1595 북쪽나라의 도로

이 문제에서 정말 중요한 조건이 있었다. '특정 도시를 두 번 이상 지나가지 않고서 임의의 두 도시 간을 이동하는 경로가 유일하도록 도로가 설계되어 있다'.라는 부분이다. 이 문장은 북쪽 나라의 도로는 트리의 형태로 되어 있다는 뜻이다. 트리에서 가장 먼 두 노드의 거리 즉, 트리의 지름을 물어보는 문제다. 트리의 지름을 구하는 3단계는 이와 같다.

1. 임의의 노드에서 가장 먼 노드를 구한다.
2. 해당 노드에서 가장 먼 노드를 찾는다.
3. 두 노드를 잇는 경로가 트리의 지름이 된다.

노드 사이의 거리는 BFS를 활용해 구했다.

import sys
from collections import deque

input = sys.stdin.readline

def BFS(start):
    dq = deque()
    dq.append([start ,0])
    visited = [False for _ in range(10001)]
    visited[start] = True
    max_d = 0
    target_node = 0
    while dq:
        cur_n, cur_d = dq.popleft()
        for next_n,next_d  in childs[cur_n]:
            if not visited[next_n]:
                visited[next_n] = True
                if (next_d:= next_d + cur_d) > max_d:
                    max_d = next_d 
                    target_node = next_n
                dq.append([next_n, next_d])
    return [target_node, max_d]
        
childs = [[] for _ in range(10001)]

while True:
    try:
        a, b, c = map(int, input().split())
        childs[a].append([b, c])
        childs[b].append([a, c])
    except:
        break
print(BFS(BFS(1)[0])[1])