[1167] 트리의 지름(BFS, 그래프)

1167번: 트리의 지름

 

분석

임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나

1. 그래프를 인접 리스트로 저장
2. BFS를 수행하고 탐색할 때 각 노드의 거리를 리스트에 저장 
3. 2에서 저장한 리스트에서 임의의 노드와 가장 먼 노드를 찾고, 그 노드부터 BFS 다시 수행
4. 3에서 저장한 거리 리스트 값 중 가장 큰 값을 이 트리의 지름으로 출력

 

풀이

"""
트리를 구성하는 노드 중 두 노드 사이의 거리가 가장 긴 것

정점개수V 
 V개의 줄에 걸쳐 간선의 정보 : 정점번호 정점번호 정점까지거리

첫째 줄에 트리의 지름을 출력
"""
from collections import deque

n=int(input()) # 노드개수
a=[[] for _ in range(n+1)] # 인접리스트
for _ in range(n):
    data=list(map(int, input().split()))
    idx=0
    s=data[idx]
    idx+=1
    while True:
        e=data[idx]
        if e==-1:
            break
        v=data[idx+1]
        a[s].append((e,v))
        idx+=2

d=[0]*(n+1) # 거리리스트
visited=[False]*(n+1)

# 완전 탐색
def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v]=True
    while queue:
        nowNode = queue.popleft()
        for i in a[nowNode]:
            nextV=i[0]
            nextW=i[1]
            if not visited[nextV]:
                visited[nextV]=True
                queue.append(nextV)
                d[nextV]=d[nowNode]+nextW

bfs(1)
max=1

for i in range(2,n+1):
    if d[max]<d[i]:
        max=i # 거리 리스트 값중 max값으로 시작점 재설정

d=[0]*(n+1)
visited=[False]*(n+1)
bfs(max)
d.sort()
print(d[n])