트리의 지름 ( 1167번 )

1167번: 트리의 지름

 

나의 풀이

from collections import deque
import sys

def _make_conn_dict(n):
    conn_dict = {i: [] for i in range(1, n + 1)}
    for _ in range(n):
        now_info = tuple(map(int, sys.stdin.readline().rstrip().split()))
        for idx in range(1, len(now_info)-1, 2):
            conn_dict[now_info[0]].append((now_info[idx], now_info[idx + 1]))
    return conn_dict

def _max_info(n, start, conn_dict):
    visit = [False] * n
    visit[start - 1] = 0
    queue = deque([(start, 0)])

    while queue:
        now_point, now_lenth = queue.popleft()
        for next_point, next_lenth in conn_dict[now_point]:
            if visit[next_point - 1] is False:
                visit[next_point - 1] = (now_lenth + next_lenth)
                queue.append((next_point, (now_lenth + next_lenth)))
    max_idx, max_value = 0, 0
    for idx in range(n):
        if (visit[idx] > max_value):
            max_idx, max_value = idx, visit[idx]
    return (max_idx + 1), max_value

n = int(sys.stdin.readline().rstrip())
conn_dict = _make_conn_dict(n)
max_start = _max_info(n, 1, conn_dict)[0]
result_max_value = _max_info(n, max_start, conn_dict)[1]
print(result_max_value)

 

시간 복잡도

_max_info(n, start, conn_dict) : bfs 탐색으로 각 구간을 돌며 lenth를 저장 ( 선형 시간 복잡도 )
해당 파이썬 시간 복잡도 : 선형 시간 복잡도 ( O(n) )