https://www.acmicpc.net/problem/1167
1167번: 트리의 지름트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지www.acmicpc.net
개념도 ㅈ같고 구현도 ㅈ같았던 문제
가장 먼져 든 생각은, 트리의 모든 정점에서 모든 정점까지의 길이를 탐색하는거였는데, 말도안되서 포기했다.
가장 중요한건 트리의 개념이다.
트리는, 어떠한 두 노드를 선택해도, 경로는 항상 하나이다.
따라서, 임이의 한 점에서 가장 먼 정점은, 트리의 지름(가장 먼 정점) 의 두 정점 중 하나이다.
더욱 자세한 설명 참고 https://blog.myungwoo.kr/112 <- 진짜 천재인듯
따라서 한 점에서 (나는 1로 함) 최대거리인 정점 one을 구한다. (이왕 구하는 김에 최대거리까지 구한다.)(bfs)
그리고 bfs를 재사용하여 그 한 점에서 최대거리인 정점(이건 필요x)과 최대거리를 구한다.
이 최대거리가 트리의 지름이다.
심지어 그래프 입력하는것까지 ㅈ같은 문제였다. 치가떨린다.
#구현하기 어지럽다 ㅅㅂ#트리에서 임의의 한 점에서의 최대의 길이는, 항상 지름 중 하나이다!import sys
from collections import dequeinput=sys.stdin.readlinedef 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])