[백준 1167번] 파이썬 - 트리의 지름

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

1167번: 트리의 지름

 

 

# 조건

• 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.

 

입력

• 트리가 입력으로 주어진다.
• 첫 줄 -> 트리 정점 개수 V ( 2<=V<=100,000)
• 둘 째줄부터 -> V개 줄에 걸쳐 간선의 정보가 주어진다.
  • 정점 번호는 1부터 V까지
  • 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어진다.
  • 하나는 정점 번호, 하나는 그 정점까지의 거리
  • 각 줄 마지막에는 -1이 입력

 

# 접근 방법

• 각 정점 간의 거리를 기록해준다.
• 빈 배열에 자식 노드와 거리를 append 해준다.
• BFS를 이용하여 이동하는 거리를 VISITED 리스트에 기록해주며 순회하며 기록해준다.
• 이후 최댓값을 뽑아주면 될 것 같다.
• 이 때, 임의의 정점 x를 찾아서
• 가장 먼 정점 y를 찾고, y에서 가장 먼 정점 z를 찾아주면 된다.

 

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import defaultdict, deque  
  
def bfs(n): # 시작 정점 받아주기 
	# 가장 먼 노드와, 그 때의 거리 받아줄 변수
    node, max_dist = 0,0  
    visited = [0] * (V+1)  
    visited[n] = 1  
    q = deque()  
    # 시작 노드와 거리 기록  
    q.append((n,0))  
    while q:  
        now_node, dist = q.popleft()  
        if max_dist < dist:  
            max_dist = dist  
            node = now_node  
  
        for child, distance in tree[now_node]:  
            if not visited[child]:  
                visited[child] = 1  
                q.append((child, distance+dist))  
  
    return node, max_dist  
  
  
V = int(input())  
  
tree = defaultdict(list)  
  
# 간선 정보 기록해주기  
for i in range(V):  
    info = [*map(int, input().split())]  
    for j in range(1, len(info)-1, 2):  
        # 0번 인덱스는 해당 정점  
        # 마지막은 -1이므로 제외 해준다.
			tree[info[0]].append((info[j],info[j+1]))  
  
  
# 임의의 정점 x에서 가장 먼 정점 y 찾기  
random_node_x, max_dist_x = bfs(1)  
  
# 정점 y에서 가장 먼 정점 z 찾기  
random_node_y, max_dist_y = bfs(random_node_x)  
  
print(max_dist_y)