[백준] 1167 트리의 지름 python

www.acmicpc.net/problem/1167

1167번: 트리의 지름

import sys; input = sys.stdin.readline
from collections import deque
V = int(input())
G = [list() for _ in range(V + 1)]
for _ in range(V):
    node = 0
    tmp_list = list(map(int, input().split()))
    for i in range(1, len(tmp_list) - 1, 2):
        G[tmp_list[0]].append((tmp_list[i], tmp_list[i + 1]))

ans = 0
def bfs(start):
    global ans
    visit = [-1] * (V + 1)
    visit[start[0]] = 0
    q = deque([start])
    ret = (0, 0)
    while q:
        cur, w = q.popleft()
        for adj, adj_w in G[cur]:
            if visit[adj] != -1: continue
            visit[adj] = visit[cur] + adj_w
            q.append((adj, adj_w))
            if ret[1] < visit[adj]:
                ret = (adj, visit[adj])
    return ret
ret = bfs((1, 0))
ans = bfs((ret[0], 0))
print(ans[1])

다른 사람들은 dfs로 풀었는데 나는 dfs로 못풀었고 bfs로 풀었다.

아무점에서 가장 먼 노드를 찾고 그 노드에서 다시 bfs를 하면 가장 먼 거리(트리의 지름)가 나오게 된다.