[백준 1167] 트리의 지름

문제 URL

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

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.
트리를 입력받아 지름을 구해라!

아이디어

1. 임의의 지점에서 가장 먼 곳으로 이동한다.
2. 그 위치에서 가장 먼 곳이 바로 지름이 된다.

이 원리를 수학적으로 증명한 블로그가 있어 첨부합니다.

파이썬 코드

import sys

input = sys.stdin.readline

v = int(input().strip())

graph = [[] for i in range(v+1)]
visited = [False for i in range(v+1)]

for i in range(1, v+1):
  e = list(map(int, input().strip().split()))
  
  n = e[0] # 노드가 순서대로 주어지지 않을 수 있음
  for j in range(1, len(e)-1, 2):
    graph[n].append((e[j], e[j+1]))
      

st = [(1, 0)] # 임의의 노드에서 출발
visited[1] = True

node = 0
ans = 0
while st:
  cur_v, cur_cost = st.pop()

  if cur_cost > ans:
    ans = cur_cost
    node = cur_v

  for i in graph[cur_v]:
    if not visited[i[0]]:
      st.append((i[0], cur_cost+i[1]))
      visited[i[0]] = True

# 가장 먼 노드에서 다시 DFS
visited = [False for i in range(v+1)]
st = [(node, 0)]
visited[node] = True
ans = 0

while st:
  cur_v, cur_cost = st.pop()

  if cur_cost > ans:
    ans = cur_cost

  for i in graph[cur_v]:
    if not visited[i[0]]:
      st.append((i[0], cur_cost+i[1]))
      visited[i[0]] = True

print(ans)

이슈

예제 입력에서는 노드가 1,2,3,4,5번 순서로 차례대로 주어졌지만, 순서가 다를 수 있음에 주의해야 한다. 만약 노드를 순서대로 입력받도록 구현했다면 2%에서 틀릴 것이다.