[백준] 트리의 지름

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

두 정점 사이의 경로가 가장 긴 값(트리의 지름)을 구하는 것이 이번 문제의 목표입니다. 트리의 특성상 부모 노드를 하나만 가질 수 있기 때문에 하나의 부모노드에서부터 자식 노드를 연결하여 만들 수 있는 최대 경로의 길이를 정할 수 있습니다. 

dfs로 탐색해주면서 현재 노드에서 도달할 수 있는 최대 길이를 리턴해주고 현재 노드에서 만날 수 있는 상위 2개의 최대 길이를 더해주면 트리의 지름을 구할 수 있습니다. 그 이유는 현재노드를 매개로하여 만날 수 있는 두 개의 경로의 합이 곧 현재노드의 자식들간의 지름의 길이가 최대가 되는 경우이기 때문입니다.

 

#문제링크: https://www.acmicpc.net/problem/1167

import sys,os
from collections import defaultdict

# sys.stdin = open(os.curdir + "\\input.txt", "r")
input = sys.stdin.readline

graph = defaultdict(list)

n = int(input())


# 그래프 구성
for _ in range(n):
    v_info = list(map(int, input().split()))
    v = v_info[0]
    i = 1

    while v_info[i] != -1:
        to, weight = v_info[i], v_info[i + 1]
        graph[v].append((to, weight))
        i += 2


# 방문 여부 판별
visited = [False] * (n + 1)
answer = -1

# 상위 두개의 긴 경로와 현재 경로의 길이를 비교해준다.
def compare(candidate, val):
    if candidate[0] <= val:
        candidate[0], candidate[1] = val, candidate[0]
    elif candidate[1] < val:
        candidate[1] = val

# 현재 노드 V - V의 자식 노드들 간의 경로 중 최대 경로를 리턴한다.
def dfs(v, weight):
    global answer
    candidate = [0, 0]
    for next, next_weight in graph[v]:
        if visited[next]:
            continue

        visited[next] = True
        ret = dfs(next, next_weight)
        compare(candidate, ret)

    # 현재 노드 V에서 만나는 경로의 최대 길이로 갱신 ex 지식 - V - 자식의 경로
    answer = max(answer, candidate[0] + candidate[1])
    return weight + candidate[0]


visited[1] = True
dfs(1, 0)

print(answer)