[백준] 1967 트리의 지름 python3

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

1967번: 트리의 지름

 

python3 코드

# 임의의 노드 A에서 가장 먼 노드 B는 반드시 이 트리의 지름을 구성하게 된다.
from collections import deque


def find_furthest_node(start):
    max_index = start
    max_value = 0

    queue = deque()
    queue.append(start)

    distances = [-1 for _ in range(n+1)]
    distances[start] = 0

    # bfs
    while queue:
        # 노드를 가져와서
        current = queue.popleft()
        # 그 이웃들을 찾고
        neghibors = graph[current]
        # 그 이웃들에 대하여
        for neghibor in neghibors.keys():
            # 방문한 적 없는 노드면
            if distances[neghibor] == -1:
                # 거리를 더하고
                distances[neghibor] = distances[current] + neghibors[neghibor]
                # 큐에 그 이웃을 추가
                queue.append(neghibor)
                # 최댓값인지 판별
                if max_value < distances[neghibor]:
                    max_index = neghibor
                    max_value = distances[neghibor]

    return (max_index, max_value)


n = int(input())
graph = {}
for i in range(1, n+1):
    graph[i] = {}

# 그래프 그리기
for _ in range(n-1):
    v, u, weight = map(int, input().split(" "))
    graph[v][u] = weight
    graph[u][v] = weight

# 노드 1에서 가장 먼 노드 B 찾기
v = find_furthest_node(1)
u = find_furthest_node(v[0])

print(u[1])

 

풀이

트리의 지름을 구하는 공식을 알면 bfs로 간단히 풀 수 있는 문제다.

임의의 노드A에서 가장 거리가 먼 노드B를 구하고, 이 노드B 에서 가장 거리가 먼 노드C를 구하면, 노드 B와 C사이의 거리가 트리의 지름이다.

 

따라서 거리를 저장하는 distance 리스트를 둔 뒤, bfs를 활용해서

1. 임의의 노드(여기선 root)에서의 가장 거리가 먼 노드 B를 찾고
2. 같은 로직으로 B에서 제일 먼 노드 C를 찾아서
3. 그 사이 거리를 return 해준다.

증명

임의의 노드를 x, x에서 가장 먼 노드를 y, 트리의 지름을 이루는 노드를 각각 v와 u라고 정의하면, 다음과 같은 경우가 존재한다.

1. x가 v 또는 u인 경우
2. y가 v 또는 u인 경우
3. x, y, v, u 가 서로 다른 경우

1, 2의 경우 공식은 올바르게 작동한다. 따라서 귀류법을 통해 3이 거짓임을 증명하여 공식이 옳음을 증명해보겠다.

 

경우3은 다음과 같이 나눌 수 있다.

경우3

a. x-y를 잇는 간선과 v-u를 잇는 간선이 겹치지 않는 경우

b. 두 간선이 서로 겹치는 경우

 

경우a는 성립하지 않는다. d(a, b)를 a-b간의 거리라고 할 때, 경우a에서는 d(x, y) < d(x, u) 혹은 d(x, v)이기 때문에 거짓이다.

경우a. d(x, u)가 더 멀다.

 

경우b를 다음과 같이 다시 그리고, 겹치는 노드를 t라고 정의해보자.

 

경우b

d(x, y) = d(x, t) + d(t, y) 이며, d(x, y)가 최댓값이 되기 위해서는 어떤 노드s에 대하여 항상 d(t, y) > d(t, s) 가 되어야 한다.

따라서 d(t, y) > d(t, v) 이고 d(t, y) > d(t, u) 이다.

하지만 이러면 d(v, u) = d(v, t) + d(t, u) 가 트리의 지름이 될 수 없기에 이 가설은 거짓이다.