1967

날짜 : 2023. 03. 14

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10**9)

n = int(sys.stdin.readline())
graph = [[] for _ in range(n + 1)]


def dfs(now, d):  # 노드번호, 길이
    for i in graph[now]:
        if dist[i[0]] == -1:  # 길이 최신화 x
            dist[i[0]] = d + i[1]
            dfs(i[0], d + i[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])

# 1번 노드에서 가장 먼 노드를 찾는다
dist = [-1] * (n + 1)
dist[1] = 0  # 본인 노드
dfs(1, 0)

# 가장 먼 노드의 인덱스 확인
start = dist.index(max(dist))
dist = [-1] * (n + 1)
dist[start] = 0
dfs(start, 0)

print(max(dist))  # start 에서 가장 먼 노드를 찾고 그 길이 리턴 -> 지름

 

 

풀이

- 지름을 구하는 경우는 다음과 같다.

1. 트리에서 정점 x를 찾는다.

2. 정점 x에서 가장 긴 거리에 있는 정점 a를 찾는다.

3. 정점 a에서 가장 긴 거리에 있는 정점 b를 찾는다.

지름은 a와 b를 잇는 경로의 길이이다.

 

- 각 노드간 거리를 파악하기 위해 방향성이 없는 그래프를 만들고 임의의 노드(코드에서는 1)를 기준으로 dfs를 실행한다.

- 이후 해당 노드에서 가장 먼 거리에 있는 노드(start)를 찾고 그 노드를 기준으로 dfs를 실행 -> 가장 먼 거리의 노드를 찾는다.

- 그리고 start와 이를 기준으로 dfs를 돌려 나온 노드간 거리가 이 트리의 길이가 된다.

 

 

알게된 점

- 트리의 지름을 구하는 원리를 찾지 못해 꽤 많이 고민했다.

- 각 노드를 기준으로 가장 먼 거리의 노드 2개를 구해서 해볼까 했는게 구현방식이 떠오르지 않았다.

 

 

 

참고 사이트

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

[백준 / Python] 1967 트리의 지름 - Kyun2da Blog

- 트리의 지름 구하는 원리(귀류법으로 증명) : https://blog.myungwoo.kr/112

트리의 지름 구하기