1967 - 트리의 지름

LeeKyoungChang·2022년 3월 7일

Graph baekjoon plzrun

Algorithm

목록 보기

59/203

📚 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))