[BOJ] 1967. 트리의 지름

www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

문제: 주어진 트리에서 트리의 지름을 구하여라

 

문제 이해하기!!

해당 문제는 1167번 문제와 같은 문제입니다.문제의 설명과 풀이 방법은 이전 글을 참고하시거나 해당 링크를 따라가시면 됩니다!링크: https://txegg.tistory.com/166

[BOJ] 1167. 트리의 지름

 

코드:

from collections import defaultdict
from heapq import *
from sys import stdin
input = stdin.readline


N = int(input())
tree = defaultdict(list)

def dfs(s):
    S = tree[s][:]
    res = 0
    nss = 0
    visit[s] = True
    while S:
        nc, ns = S.pop()
        if visit[ns]:
            continue
        visit[ns] = True
        for xc, xs in tree[ns]:
            S.append((xc + nc, xs))
        if res < nc:
            res = nc
            nss = ns
    if s == 1:
        return nss
    else:
        return res

for _ in range(N-1):
    a, b, c = map(int, input().split())
    tree[a].append((c, b))
    tree[b].append((c, a))

visit = [False] * (N+1)
ns = dfs(1)
visit = [False] * (N+1)
print(dfs(ns))