백준 1595 : 북쪽나라의 도로 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS(Node):
    visit[Node]=True
    for i,j in Tree[Node]:
        if not visit[i]:
            distance[i]+=distance[Node]+j
            DFS(i)


Tree=[ [] for _ in range(10001) ]

while True:
    try:
        u,v,k=map(int,input().split())
        Tree[u].append((v,k))
        Tree[v].append((u,k))
    except:
        break

visit = [False] * (10001)
visit[1]=True
distance=[0]*(10001)

DFS(1)
New_start=distance.index(max(distance))

visit = [False] * (10001)
visit[New_start]=True
distance=[0]*(10001)

DFS(New_start)
print(max(distance))

📌 어떻게 접근할 것인가?

총 2번의 접근을 하였습니다. 처음에는 그냥 모든 노드들을 루트노드라고 생각해서 완전탐색을 했습니다. 하지만 시간초과가 발생했습니다.

두번째로는 리프노드에서만 출발을 하였습니다. 하지만 이것도 시간초과가 발생하였습니다.

문제에서 중요한 것은 거리가 가장 먼 두 도시 사이의 거리 입니다. 가만히 생각해보면 이것을 구하는 문제가 있습니다. 바로 트리의 지름 입니다.

트리의 지름 을 통해서 임의의 가장 긴 두 정점의 거리 를 구할 수 있습니다.

따라서 트리의 지름을 구현해주시면됩니다.

처음 시작점은 아무거나 잡으셔도 상관없습니다.