📚 1967 - 트리의 지름

트리의 지름

이해

처음 접해보는 문제였다.
트리의 지름을 구하는 방법 증명 과정 참고
설명 잘되어 있다!

트리가 입력으로 주어진다.

📣 트리의 지름 구하기 공식
(1) 루트 노드에서 가장 먼 노드를 찾는다. (가장 먼 노드 : a)
(2) a에서 가장 먼 노드를 찾는다. (a에서 가장 먼 노드 : b)
(3) a - b가 트리의 지름이 된다.

✔️ 알게된 내용
문제를 풀 때, 감이 오지 않는다면 바로 구글링을 한다.
구글링을 해서 어떻게 풀어야 하는지 감을 잡는다.

dfs에서 시작 노드를 기준으로 방문한 노드간의 거리를 알고 싶을 때
➡️ dfs를 구현할 때는 시작 전, distance[-1] * n을 생성한다. → 현재 시작 노드, 다음으로 방문한 노드라면 거리를 distance[다음으로 방문한 노드] 에 (현재 시작 노드에서 다음으로 방문한 노드까지 거리를) 저장한다. → 다음 시작 노드, 다다음으로 방문한 노드라면 거리를 distance[다음으로 방문한 노드] = 이전 distance + (다음 방문 노드와 다다음 방문한 노드까지 거리)를 더한다.

소스

import sys

sys.setrecursionlimit(10**9)

n = int(sys.stdin.readline())

graph = [[] for _ in range(n + 1)]

# 트리 구현
for _ in range(n - 1):
    a, b, c = map(int, sys.stdin.readline().split())

    graph[a].append([b, c])  # 부모에서 자식
    graph[b].append([a, c])  # 자식에서 부모


def dfs(num, wei):
    for i in graph[num]:
        a, b = i
        if distance[a] == -1:
            distance[a] = wei + b
            dfs(a, wei + b)


# 1번 노드에서 가장 먼 곳을 찾는다.
distance = [-1] * (n + 1)
distance[1] = 0
dfs(1, 0)

# 찾은 노드에서 가장 먼 노드를 찾는다.(인덱스 반환)
first_result = distance.index(max(distance))
distance = [-1] * (n + 1)
distance[first_result] = 0
dfs(first_result, 0)

print(max(distance))

채점 결과

• 보통 간단한 코드상에서는 python3가 메모리, 속도측에 우세하기 때문에 사용한다.
• pypy3는 메모리를 조금 더 사용하여 그것들을 저장하고 있어, 실행속도를 개선할 수 있다.

이 문제와 같이 메모리 공간을 많이 사용하는 소스라면 python3로 제출해야 한다.

참고

• https://kyun2da.github.io/2021/05/04/tree's_diameter/