[탐색/DFS] 백준 1967 트리의 지름 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1967번: 트리의 지름

 

 

 

2. 문제 풀이

 트리의 양 끝단의 거리를 재는 문제입니다. 즉, 가장 먼 노드 간의 거리를 재야 합니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

[Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

 루트 노드가 주어지지 않기 때문에, 총 2번의 탐색이 필요합니다.

 

1) 1번 노드(어떤 노드든 괜찮음)에서 가장 먼 노드를 dfs 탐색으로 찾아냅니다.
2) 찾아낸 노드에서 가장 먼 노드를 찾아서 거리를 측정합니다. 

 

 

 

3. 코드

import sys
sys.setrecursionlimit(10**9)  # dfs 반복횟수 제한 해제
input = sys.stdin.readline

# 입력
n = int(input())
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
    parent, child, weight = map(int, input().split())
    graph[parent].append([child, weight])
    graph[child].append([parent, weight])

# dfs
def dfs(x, dist):
    for i in graph[x]:
        node, wei = i
        if distance[node] == -1:
            distance[node] = dist + wei
            dfs(node, dist + wei)

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

# 찾은 노드에서 가장 먼 노드를 찾음
res = distance.index(max(distance))
distance = [-1] * (n+1)
distance[res] = 0
dfs(res, 0)

# 출력
print(max(distance))

 dfs 탐색과 관련된 설명과 코드는 위 링크에서 보실 수 있습니다.