백준 1967번(트리의 지름) 파이썬

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

1967번: 트리의 지름

이 문제를 보고 "어?! 다익스트라로 풀면 되겠네" 하고 바로 다익스트라로 풀었는데 시간초과가 나와버렸다.

즉, 알고리즘 선택이 잘못된 것이였다. 그래서 dfs겠는데 하고 풀어보려 했지만 결국 풀 수가 없었다. 그래서 결국 구글링을 해보던 도중에 접근 방법을 알게됐다. 우선, 그래프의 특징을 알아야 한다. 

트리의 노드중 아무거나 하나 선택한다. 그리고 그 노드로부터 가장 먼 거리에 있는 노드를 선택한다. 그리고 가장 먼 거리에 있던 노드에서 또 한번 가장 먼거리에 있는 노드를 탐색한다. 그럼 첫노드와 마지막 노드의 거리가 이 그래프의 지름이 되게 된다.

이 원리를 알아야 풀 수 있는 문제인거 같다. 나 또한 이 원리를 알지 못했고 그래서 풀 수가 없었던거 같다. dfs를 2번 써서 풀 게 되었다.

아래는 풀이 코드이다.

 

import sys
sys.setrecursionlimit(10**9) # 이 문제에선 해주지 않았더니 recursionerror가 떴다.
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))# 무방향 그래프이므로
    graph[b].append((a,c))# 두 노드 모두에 추가시켜준다.

distance = [-1]*(n+1) #거리를 나타낼 리스트이다.

def dfs(start,cost):
    for i,j in graph[start]: # 해당 노드의 요소를 뺀다
        a,b = i,j # 각각 a,b에 매칭시킨다
        if distance[a] == -1: # 방문하지 않았을경우
            distance[a] = b + cost # 해당 노드의 거리값과 출발한 노드의 간선의 값을 합해서 넣어준다
            dfs(a, b+cost) # 재귀를 해준다

distance[1] = 0 # 1번 노드부터 탐색해준다 
dfs(1,0)

node = distance.index(max(distance))# 첫번째 탐색이 끝나고 가장 멀리있는 노드를 찾아준다.
distance = [-1]*(n+1)
distance[node] = 0 # 가장 멀리있는 노드에서부터 다시 탐색한다
dfs(node,0)

print(max(distance)) # 최댓값 출력!!