[백준 1167번] 트리의 지름

문제 출처

문제 유형

• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색

풀이

해당 문제는 solved.ac 사이트 기준 골드 2 문제입니다.

트리 사이에서 가장 거리가 먼 정점의 사이 거리를 구하는 문제입니다. 1967번 문제와 같은 방식으로 해결하는 문제입니다.

• 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다

• 각 줄의 마지막에는 -1이 입력으로 주어진다.

• 주어지는 거리는 모두 10,000 이하의 자연수이다.

1967번 문제와 마찬가지로 모든 정점의 거리를 일일이 조사하기 보다는 특정 노드에서 가장 기이가 긴 노드를 선택하고, 그 노드에서 가장 길이가 긴 노드를 선택해 값을 구하는 방식입니다. 해당 방법의 증명식은 https://koosaga.com/14 에서 확인했습니다.

풀이 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

v = int(input())

# 배열 저장 트리
tree = [[] for _ in range(v+1)]

def dfs(start, depth):
    for n, d in tree[start]:
        # 아직 방문하지 않은 정점
        if distance[n] == -1:
            distance[n] = d + depth
            dfs(n, distance[n])

for _ in range(v):
    arr = list(map(int, input().split()))

    for x in range(len(arr)-1):
        # 특정 조건으로 정점 및 간선 구별
        if x % 2 == 1:
            tree[arr[0]].append((arr[x], arr[x+1]))

# 루트에서 가장 먼 정점 구하기
distance = [-1 for _ in range(v+1)]
distance[1] = 0
dfs(1, 0)

# 가장 먼 정점 인덱스 가져오기
maxIndex = distance.index(max(distance))

# 가장 먼 정점에서 가장 먼 정점 구하기
distance = [-1 for _ in range(v+1)]
distance[maxIndex] = 0
dfs(maxIndex, 0)

print(max(distance))