백준 1967 트리의 지름 (Python)

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

1967번: 트리의 지름

원래 푸는 방법대로 풀지 않은 거 같다.

 

원래는 1번 노드에서 가장 먼 곳을 찾은 후, 그 노드에서 가장 먼 곳과의 거리를 구하면 된다.

그러면 노드에서는 지름을 구할 수 있다.

 

하지만 그냥 아무생각없이 모든 노드를 방문하는 방법으로 풀었는데, 그냥 풀렸다.

그래서 이번 문제는 그냥 간단하게 푸는 방법으로 풀도록 하겠다.

 

이번에는 그래프를 dict로 받았는데, 모든 노드에 대한 2차원 배열로 만들면 메모리 초과가 발생한다.

 

그냥 반복마다, 최대의 길이를 구하고 그 중에서 최대의 길이를 출력한다.

import sys
from collections import deque

n = int(sys.stdin.readline().strip())

node = {i: [] for i in range(n)}

for i in range(n - 1):
    start, end, weight = map(int, sys.stdin.readline().split())

    node[start - 1].append([end - 1, weight])
    node[end - 1].append([start - 1, weight])

result = 0

for i in range(n):
    cur_result = 0
    visited = [False for _ in range(n)]
    need_visit = deque()
    need_visit.append([0, i])
    visited[i] = True

    while need_visit:

        cur_weight, cur_node = need_visit.popleft()

        cur_result = max(cur_result, cur_weight)

        for next_node, next_weight in node[cur_node]:
            if visited[next_node] is False:
                visited[next_node] = True
                need_visit.append([cur_weight + next_weight, next_node])

    result = max(result, cur_result)

print(result)