백준 1167 트리의 지름 (Python)

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

1167번: 트리의 지름

트리의 지름을 구하는 방법은 우선, 한 노드에서 가장 멀리 있는 노드를 구한다.

그리고 그 노드에서 가장 멀리 있는 길이를 구한다.

그러면 그게 노드의 지름이 된다.

 

그러면 2번 길이를 구해야 하는 데, 귀찮아서 함수로 만들어버렸다.

 

우선 각 그래프에 대한 정보를 입력 받은 후 BFS를 진행한다.

 

처음의 BFS에서는 가장 멀리 있는 노드를 구하고, 그 다음의 BFS에서는 길이를 구한 후 출력한다.

 

from collections import deque
import sys

V = int(sys.stdin.readline())

graph = [[] for _ in range(V + 1)]

for _ in range(V):
    c = list(map(int, sys.stdin.readline().split()))
    for e in range(1, len(c) - 2, 2):
        graph[c[0]].append((c[e], c[e + 1]))


def bfs(target):
    weight = [-1] * (V + 1)
    weight[target] = 0
    need_visit = deque()
    need_visit.append(target)
    result = [0, 0]

    while need_visit:
        cur = need_visit.popleft()
        for v, w in graph[cur]:
            if weight[v] == -1:
                weight[v] = weight[cur] + w
                need_visit.append(v)
                if result[0] < weight[v]:
                    result = [weight[v], v]

    return result


print(bfs(bfs(1)[1])[0])