[파이썬] [그래프] 백준 1167 트리의 지름

문제

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

1167번: 트리의 지름

코드

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

def bfs(start):
    visited=[-1]*(v+1)
    queue=deque()
    queue.append(start)
    visited[start]=0
    max_a=[0,0]  #dis, node

    while queue:
        t=queue.popleft()
        for i in graph[t]:
            if visited[i[0]]==-1:
                visited[i[0]]=visited[t]+i[1]
                queue.append(i[0])
                if max_a[0]<visited[i[0]]:
                    max_a[0]=visited[i[0]]
                    max_a[1]=i[0]
    return max_a

v=int(input())

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

for _ in range(v):
    a=list(map(int, input().split()))
    i=1
    while a[i]!=-1:
        graph[a[0]].append([a[i],a[i+1]])
        i+=2

dis, node=bfs(1)
dis, node=bfs(node)

print(dis)

생각 정리

트리의 지름은 아무 노드에서 bfs(dfs도 무관)를 통해 가정 멀리있는 노드를 구한 후 해당 노드에서 bfs를 한번더 진행하여 가장 멀리있는 노드를 구하면 된다.