[백준BOJ] 1167번 트리의 지름.py

 

백준 저지에서 트리의 지름을 파이썬을 통해 풀어 보았다. 

 

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

1167번: 트리의 지름

1167번 트리의 지름.py

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1167번 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

설명

트리의 지름을 구하는 문제이다. 보통 BFS나 DFS로 푸는 것 같은데 정점간의 거리에서 바로 다익스트라가 생각나서 다익스트라로 풀었다. 

 

이 문제를 풀기 위해서는 코드를 구현하기에 앞서 트리의 지름을 구하는 방법을 알아야 한다. 어떤 한 정점에서 가장 멀리 있는 정점 x를 구하고, 정점 x에서 가장 먼 거리에 있는 정점 y를 구했을 때 x와 y의 거리가 트리의 지름이다. 이 내용은 별도의 증명을 알고 있지 않으면 생각해내기 힘들다. 물론 모든 정점을 돌아보며 비교해가며 구할 수는 있지만 그런식으로는 시간 초과를 피할 수 없다.

 

다익스트라를 통해 1번 정점에서 가장 멀리 있는 정점을 구한다. 그리고 해당 정점에서 또 다시 다익스트라를 통해 모든 정점에 대한 거리를 구한다. 그 중 가장 큰 값이 정답이다.

코드

#1167번 트리의 지름.py
import heapq
import sys
input = sys.stdin.readline
def dijkstra(start) : 
    q=[]
    root[start]=0 #자기 자신에게 가는 것은 0
    heapq.heappush(q,(0,start)) #힙에 비용, 출발 노드 저장

    while q :
        cost, now = heapq.heappop(q)  # 가장 작은 가중치를 가진 노드 선택
        if root[now] < cost : #선택한 노드의 가중치가 이미 저장된 가중치보다 크면 실행x
            continue
        for next in graph[now] : 
            next_cost = cost+next[1] #현재 노드에서 다음 노드까지 가중치 계산
            if next_cost < root[next[0]] : #가중치가 더 작으면 
                root[next[0]]=next_cost #갱신
                heapq.heappush(q,(next_cost,next[0]))#heap에 추가

V =int(input())
graph = [[]for _ in range(V+1)]

for i in range(V):
    temp = list(map(int,input().split()))
    j=1
    while temp[j]!=-1:
        graph[temp[0]].append([temp[j],temp[j+1]])
        j+=2

diameter = 0
root = [int(1e9)]*(V+1)
root[0] = 0
dijkstra(1)
temp = max(root)
index = root.index(temp)

root = [int(1e9)]*(V+1)
root[0] = 0
dijkstra(index)
diameter = max(root)
print(diameter)