[PS] 1167. 트리의 지름

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

1167번: 트리의 지름

---

문제 요약

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

---

문제 접근

첫번 째, (실패)

DFS를 이용하여 1~n까지의 노드에 대해 각각 가장 거리가 먼 노드까지의 거리를 구한 후, 구한 값 중 MAX값을 출력하도록 하였다. 정답은 나오지만, 시간초과가 발생하였다...

파이썬이라서 안되는건가? 하고 PyPy3로 시도하여도 시간초과가 발생하여서 다른 접근 방법을 찾다가 결국 검색을 시도했다.. , ,,, ㅜ

 

두번 째, (성공)

검색결과, 빠른 시간내에 풀 수 있는 가장 핵심적인 원리를 알게되었다..!

 

A-B까지의 거리를 트리의 지름이라고 할 때, 각 노드에서 가장 멀리 떨어져 있는 노드까지의 경로의 일부는 A-B까지의 경로와 겹친다!!! 이 원리로 시뮬레이션을 돌려보면, 어느 노드에서 출발하여도 가장 멀리 떨어진 노드는 A or B인 것을 알 수 있다.

 

따라서, DFS를 두번 돌리는 것으로 변경하였다.

임의의 노드에서 A 혹은 B를 구한 후, 만약 A라면 B까지의 거리를, B라면 A까지의 거리를 구하도록 했다.

 

import sys
from collections import deque

V = int(sys.stdin.readline())
tree = [dict() for v in range(V+1)]
for v in range(V):
  input_list = list(map(int, sys.stdin.readline().split()))
  it = iter(input_list)
  index = next(it)
  num = next(it)
  while (num != -1):
    tree[index][num] = next(it)
    num = next(it)

def far_point(start):
  max_cost = 0
  end_num = start
  cost = [0 for v in range(V+1)]
  stack = deque()
  stack.append(start)
  record = set()

  while (stack):
    now = stack.pop()
    if cost[now] > max_cost:
      max_cost = cost[now]
      end_num = now
    if now not in record:
      record.add(now)
      for to in tree[now].keys():
        if to not in record:
          stack.append(to)
          cost[to] = cost[now] + tree[now][to]
  
  return max_cost, end_num

print(far_point(far_point(1)[1])[0])

다음부턴,, 문제를 풀기전에 생각을 더하고 제출해봐야겠다