백준 1167 트리의 지름

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

1167번: 트리의 지름

개념도 ㅈ같고 구현도 ㅈ같았던 문제

가장 먼져 든 생각은, 트리의 모든 정점에서 모든 정점까지의 길이를 탐색하는거였는데, 말도안되서 포기했다.

가장 중요한건 트리의 개념이다.

 

트리는, 어떠한 두 노드를 선택해도, 경로는 항상 하나이다.

따라서, 임이의 한 점에서 가장 먼 정점은, 트리의 지름(가장 먼 정점) 의 두 정점 중 하나이다.

더욱 자세한 설명 참고 https://blog.myungwoo.kr/112 <- 진짜 천재인듯

 

따라서 한 점에서 (나는 1로 함) 최대거리인 정점 one을 구한다. (이왕 구하는 김에 최대거리까지 구한다.)(bfs)

그리고 bfs를 재사용하여 그 한 점에서 최대거리인 정점(이건 필요x)과 최대거리를 구한다.

이 최대거리가 트리의 지름이다.

 

심지어 그래프 입력하는것까지 ㅈ같은 문제였다. 치가떨린다.

 

#구현하기 어지럽다 ㅅㅂ
#트리에서 임의의 한 점에서의 최대의 길이는, 항상 지름 중 하나이다!

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


def bfs(start): 
    one=0
    max_val=0
    visited=[-1 for _ in range(v+1)]
    visited[start]=0

    que=deque([start])
    
    while que:
        now=que.popleft()
        for next,weight in arr[now]:
            if visited[next]==-1:
                visited[next]=visited[now]+weight
                if visited[next]>max_val:
                    one=next
                    max_val=visited[next]
                que.append(next)
    return one,max_val #(지름의 정점중 1, <-까지의 최댓값 )
            
    


    


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

for _ in range(v):
    tmp=list(map(int,input().strip().split()))
    
    current=tmp[0]
   
    for i in range(1,len(tmp)-1,2):
        arr[current].append([tmp[i],tmp[i+1]])
        #어지럽다진짜

one,max_val=bfs(1)
print(bfs(one)[1])