1967 백준 파이썬

이 문제를 풀려면 어떤 임의의 점에서 가장 많이 떨어진 점은 지름의 한 점에 해당한다는 점을 알고 있어야 한다.

그림을 통해 보면

원 내부의 직선에서 어떤 점을 잡든, 그 점에서 가장 먼 점은 원의 지름의 한 끝에 해당하는 점이 된다.

그리고, 그 점에서 가장 먼 점을 찾아 연결하면 그것이 바로 원의 지름에 해당한다.

 

따라서 이런 트리가 있다고 가정해 보자.

이 노랑색 루트 노드에서 가장 먼 점은 빨강색 노드이다.

그리고 빨강 노드에서 가장 멀리 떨어진 점을 찾는다. 이게 바로 파란색 점이다.

bfs를 통해 해결했다.

다익스트라를 통해 해결해도 문제 없을 것 같다.

from collections import deque
n=int(input())
tree=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    tree[a].append((b,c))
    tree[b].append((a,c))
def bfs(s):
    res,resgo=0,0
    q=deque()
    q.append((s,0))
    vis=[0 for x in range(n+1)]
    vis[s]=1
    while q:
        where, dis=q.popleft()
        for x in tree[where]:
            next=x[0]
            cost=x[1]
            if vis[next]==0:
                vis[next]=1
                q.append((next,dis+cost))
                if dis+cost>res:
                    res=dis+cost
                    resgo=next
    return resgo,res
where,cost=bfs(1)
where,result=bfs(resgo)
print(result)