Baekjoon 1167. 트리의 지름 / Python

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

 

문제 설명

1. 트리의 지름의 최댓값을 구하는 문제이다.

문제 풀이

1. 트리의 임의의 한 점에서 각 노드로 가는 최댓값을 구한다. → 트리의 지름에 해당하는 두 노드를 a와 b라고 했을 때, 임의의 한 노드에서 다른 임의의 한 노드까지의 거리의 최댓값에 해당하는 노드는 항상 a이거나 b이다.
2. bfs를 두 번 돌린다. → a혹은 b를 찾고 → 다시 최대 경로를 구해서 지름을 구한다.

풀이 코드

from collections import deque as dq
import sys; input = sys.stdin.readline

def bfs(v, arr, s):
    q = dq()
    q.append((s, 0))
    visit = [-1] * (v + 1)
    visit[s] = 0
    res = [0, 0]

    while q:
        now, dist = q.popleft()
        for n_next, dist_next in arr[now]:
            if visit[n_next] == -1:
                sum_dist = dist + dist_next
                q.append((n_next, sum_dist))
                visit[n_next] = sum_dist
                if res[1] < sum_dist:
                    res[0], res[1] = n_next, sum_dist
    return res

v = int(input())
arr = [[] for _ in range(v + 1)]

for _ in range(v):
    graph = list(map(int, input().split()))
    v_cur = graph[0]
    i = 1
    while True:
        if graph[i] == -1:break
        e, w = graph[i], graph[i + 1]
        arr[v_cur].append((e, w))
        i += 2

print(bfs(v, arr, bfs(v, arr, 1)[0])[1])