트리의 지름

트리에서 임의의 두 점 사이의 거리 중 가장 긴 거리를 찾는 문제이다. 플로이드 와샬 알고리즘을 사용해 푸는 문제라고 생각하고 접근했는데, 메모리 초과가 발생해 해결하지 못했다.

그래서 몇 번의 시도 끝에 검색을 해 봤더니, 트리의 지름을 구하는 별도의 (공간복잡도와 시간복잡도가 낮은)방법이 존재했다.

트리의 지름을 구하는 방법에 대해 간단하게 짚고 넘어가보자.

  • 트리에서 임의의 Node_1를 하나 선택한다.
  • Node_1에서 가장 먼 Node_2를 찾는다.
  • Node_2에서 가장 먼 Node3를 찾는다. 이 두 Node 사이의 거리가 트리의 지름이다.

증명 방법은 인터넷의 다른 블로그들을 참고하길 바란다. (아직 온전히 내것으로 만들지 못했기도 하고, 여기서 다루기엔 다른 블로그들의 컨텐츠를 배껴오는 것 밖에 되지 않을것 같았다. 다음 기회에 한 번 더 다뤄보자.)

임의의 점에서 가장 먼 Node를 구할 때는, 다익스트라 알고리즘을 사용했다.

다익스트라 알고리즘에 대해서는 따로 포스팅해 놓았다. 아래의 글들을 참고하자.

CODE

import sys
import heapq
from collections import deque
read = sys.stdin.readline
inf = sys.maxsize

v = int(read())
bridge = dict()
for _ in range(v):
    tmp = list(map(int, read().split()))
    bridge[tmp[0]-1] = []
    i = 1
    while True:
        if tmp[i] == -1:
            break
        bridge[tmp[0]-1].append([tmp[i+1], tmp[i]-1])
        i += 2

# x Node로 부터 가장 먼 점의 거리 & 좌표 추출 - 다익스트라 알고리즘 활용


def bfs_far(x):
    # 가장 먼 점의 거리, 좌표 저장
    save = [0, 0]
    # 거리 저장
    check = list(inf for _ in range(v))
    check[x] = 0

    # 최단거리의 아직 방문하지 않은 점들 부터 탐색해나가기 위해 거리정보를 앞에 저장한다.
    hq = [[0, x]]
    heapq.heapify(hq)
    while hq:
        w, n = heapq.heappop(hq)
        # w가 기존에 저장된 거리보다 크다면, save값을 갱신한다.
        if w > save[0]:
            save = [w, n]
        for b in bridge[n]:
            if check[b[1]] == inf:
                check[b[1]] = min(check[b[1]], b[0]+w)
                heapq.heappush(hq, [check[b[1]], b[1]])
            # check의 값이 업데이트 된 점의 경우에는 이미 hq에 추가되어 있기 때문에 다시 추가하지 않는다.
            else:
                check[b[1]] = min(check[b[1]], b[0]+w)

    return save


# 반드시 1부터 탐색해야할 필요는 없다. 어떤 Node 부터 탐색하더라도 결과는 같다.
x = bfs_far(0)
answer=bfs_far(x[1])[0]
print(answer)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]