BOJ 1167 트리의 지름 Python

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

트리의 지름을 구하는 방법은 다음과 같다.
1. 아무 정점이나 잡아 DFS 를 이용해 그 점(시작점)으로 부터 가장 먼 정점을 구한다.거리가 동일한 정점이 여러 개라면 아무 정점이나 골라도 괜찮. 이렇게 골라진 가장 먼 정점을 x라고 하자.
2. DFS 를 이용해 동일한 방식으로 x 를 시작점으로 하였을 때 가장 먼 정점을 구한다. 이 때 구해진 거리가 지름이 됨

근데 왜 이렇게 구한 것이 트리의 지름이라고 할 수 있을까?
그것의 증명은 귀류법을 통해 가능하다.

임의의 정점 x 로 부터 가장 먼 정점의 번호를 y 라 하고, y로 부터 가장 먼 정점의 번호를 z라고 했을 때,
결국 y 와 z 를 잇는 경로가 트리의 지름이 된다는 것인데

이를 증명하려면 귀류법을 통해, 즉, y 정점이 트리의 지름에 포함이 되지 않는다고 가정했을 때 모순을 보이면 된다.(모순 -> y 정점이 트리의 지름에 반드시 포함됨)

임의의 정점 u와 정점 v 를 연결하는 연결하는 경로가 트리의 지름인 경우에 대해 생각을 해보자.

1) x 와 u 가 동일한 경우

   x/u
  / \
 y   v

이 경우 dist(u, v) 가 dist(x, y)가 되므로 y가 지름에 포함되게 된다 이는 가정과 모순

2) x-y, u-v 경로의 일부가 겹치는 경우

   x
    \
     u
    / \
   /   y
  /     
 v       

x에서 y 까지 경로가 x 에서 가장 긴 경로라고 가정하였음. 만약 u-v 가 지름이라면, 그 길이는 x-y 보다 길거나 같아야 함. 그러나 x에서 y까지의 경로가 이미 가장 긴 경로라고 가정했으므로 u-v 의 길이는 x-y의 길이와 같아야 함.
이 경우 y 는 반드시 u-v 경로에 포함되어 있어야 하며, 이로 이로 인해 y는 트리의 지름에 포함되게 됨. 즉, 모순

3) x-y, u-v 경로가 아예 독립적일 경우

 u
 / \
x   v
 \
  y

독립적임에도 불구하고, x 에서 가장 먼거리가 y가 되고, u-v가 지름이 되려면, x에서 u 또는 v 까지의 거리는 x-y보다 길어야 함. 그러나 이는 x- y 가 x에서 가장 먼 거리라는 초기 가정에 모순 됨

정답 코드)

import sys
sys.setrecursionlimit(10**6)

si = sys.stdin.readline

MAX = 100_000

n = int(si())
node = [[] for _ in range(MAX + 1)]
visited = [False] * (MAX + 1)
max_len = 0
max_len_point = 0


def dfs(point, length):
    global max_len, max_len_point

    if visited[point]:
        return

    visited[point] = True
    if max_len < length:
        max_len = length
        max_len_point = point

    for i in range(len(node[point])):
        dfs(node[point][i][0], length + node[point][i][1])


for _ in range(n):
    temp_list = list(map(int, si().split()))[:-1]

    cnt = 0
    parent = temp_list[cnt]

    while True:
        cnt += 1
        child_index = cnt
        cnt += 1
        length_index = cnt
        if len(temp_list) <= cnt:
            break
        child = temp_list[child_index]
        length = temp_list[length_index]

        node[parent].append((child, length))
        # 양방향 연결을 해주지 않아도 되며, 연결 하지 않는게 더 빠르다
        # node[child].append((parent, length))


# print(node)

# 가장 멀리 있는 정점(max_len_point) 구하기
dfs(1, 0)

max_len = 0

visited = [False] * (MAX + 1)

# max_len_point 와 가장 멀리 있는 정점과의 거리 구하기
dfs(max_len_point, 0)

print(max_len)

위: 단방향 그래프 제출 결과
아래: 양방향 그래프 제출 결과