[Python] 백준 1967 - 트리의 지름 문제 풀이

Overview

BOJ 1967번 트리의 지름 Python 문제 풀이
분류: tree (트리)

문제 페이지

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

풀이 코드

from sys import stdin, setrecursionlimit
from collections import defaultdict
setrecursionlimit(10 ** 9)


tree = defaultdict(list)
res = 0


def dfs(node: int) -> int:
    global res

    if not tree[node]:
        return 0

    radii = []
    for child, weight in tree[node]:
        radii.append(weight + dfs(child))
    if len(radii) > 2:
        radii.sort(reverse=True)
        res = max(radii[0] + radii[1], res)
    else:
        res = max(sum(radii), res)
    return max(radii)


def main():
    def input():
        return stdin.readline().rstrip()

    n = int(input())
    for _ in range(n - 1):
        p, c, w = map(int, input().split())
        tree[p].append((c, w))

    dfs(1)
    print(res)


if __name__ == "__main__":
    main()
    

dfs 탐색을 통해 트리의 지름을 찾는다. 문제 입력에서 이진 트리라는 조건이 없으므로 부모 노드의 자식들이 여러 개 일 수 있다는 점에 주의한다.