[Python] 백준1167 트리의 지름

02 Jul 2023 in Study on Algorithm

백준1167 트리의 지름 링크

문제

예제 입력

---

코드

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

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
    arr = list(map(int, input().split()))
    for i in range(1, len(arr) - 1):
        if i % 2 == 1:
            graph[arr[0]].append([arr[i], arr[i+1]])

def dfs(n, d):
    for i in graph[n]:
        if dist[i[0]] == -1:
            dist[i[0]] = i[1] + d
            dfs(i[0], i[1] + d)

dist = [-1] * (N+1)
dist[1] = 0
dfs(1, 0)

st = dist.index(max(dist))
dist = [-1] * (N+1)
dist[st] = 0
dfs(st, 0)

print(max(dist))

설명

파이썬을 통해서 사용자로부터 입력받아 DFS알고리즘으로 사용하여 트리의 지름를 구현했습니다.

---

결과