트리의 지름 ( 1967번 )

1967번: 트리의 지름

 

나의 풀이

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 - 1):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        conn_dict[a].append((b, c))
        conn_dict[b].append((a, c))
    return conn_dict

def _route_info(n, start, conn_dict):
    route_info = [False] * n
    route_info[start - 1], queue =0, deque([(start, 0)])
    while queue:
        now_point, now_lenth = queue.popleft()
        for next_point, next_lenth in conn_dict[now_point]:
            if (route_info[next_point - 1] is False):
                route_info[next_point - 1] = (now_lenth + next_lenth)
                queue.append((next_point, (now_lenth + next_lenth)))
    return (route_info, max(route_info)) 

def _result_max_value(n, conn_dict, route_info, max_value):
    answer = 0
    for idx in range(len(route_info)):
        if (route_info[idx] == max_value):
            answer = max(answer, _route_info(n, idx + 1, conn_dict)[1])
    return answer

n = int(sys.stdin.readline().rstrip())
conn_dict = _make_conn_dict(n)
route_info, max_value = _route_info(n, 1, conn_dict)
print(_result_max_value(n, conn_dict, route_info, max_value))

 

시간 복잡도

for idx in range(len(route_info)) : 노드를 순회 ( 선형 시간 )
	if (route_info[idx] == max_value) : 조건 맞는 노드 bfs 함수 실행 ( 선형 시간 ) 
		answer = max(answer, _route_info(n, idx + 1, conn_dict)[1])
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )