1967 트리의 지름

알고리즘 공부

문제 보기

아이디어

def bfs(i):
	노드i에서 나머지 n-1개의 노드까지의 거리를 모두 계산한다.      
	그 중 최대값을 반환

m = 0
for i in range(N):
	m = max(m, bfs(i))

bfs(i) 의 시간복잡도는 O(N) 이고 이 함수를 N번 반복하므로 전체 시간복잡도는 O(N²)이다.
1≤N≤10⁴이므로 O(N²)이면 아슬아슬하다. (C/C++ 기준 반복문을 1억번 실행하는데 1초정도 걸린다고 한다.)

정답 코드

Python3로 실행했을 때에는 시간 초과가 떠서 PyPy3로 실행했더니 통과했다.
반복횟수가 1억번에 근접하면 PyPy3를 선택해야겠다.

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

n = int(input().strip())
# adjacent list
graph = [[] for _ in range(n+1)]

for i in range(n-1):
    s,e,w = map(int, input().strip().split())
    graph[s].append((e, w))
    graph[e].append((s, w))

def bfs(start):
    visited = [False]*(n+1)
    q = deque()
    q.append(start)
    visited[start] = True
    d = [0] * (n+1)
    while q:
        v = q.popleft()
        for i in range(len(graph[v])):
            nextV = graph[v][i]         # nextV[0]: node# nextV[1]: cost
            if not visited[nextV[0]]:
                visited[nextV[0]] = True
                q.append(nextV[0])
                d[nextV[0]] = d[v] + nextV[1]
    return max(d)

m = 0
for i in range(1, n+1):
    m = max(m, bfs(i))
print(m)