99클럽 코테 스터디 17일차 TIL + Tree

문제

Baekjoon 18126: 너구리 구구

• 설명: 트리가 주어질 때 루트에서 거리가 가장 먼 노드까지의 거리를 찾아라

풀이

• $N$개의 노드가 있고, $N - 1$개의 간선이 있으며 모든 노드가 연결되어있으려면 반드시 트리 구조이다.
• 따라서 입구($1$)에서 가장 먼 위치는 단순히 모든 노드를 탐색하며 가장 먼 위치에 있는 노드까지의 거리를 구하면 된다.

오늘의 회고

• setrecursionlimit을 해두지 않아 틀렸었다.
• python 기본 재귀 깊이는 1,000이기 때문에 문제에서 주어진 5,000개의 노드를 탐색하기엔 부족하다.

Code

import sys
sys.setrecursionlimit(10_000)
input = sys.stdin.readline


def dfs(me, mom, dis):
    global ans

    ans = max(ans, dis)
    for adj_v, adj_d in adj_list[me]:
        if adj_v != mom:
            dfs(adj_v, me, dis + adj_d)


n = int(input())

adj_list = [[] for _ in range(5_001)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())

    adj_list[a].append((b, c))
    adj_list[b].append((a, c))

ans = 0
dfs(1, 0, 0)

print(ans)

필수 해시태그: # # # # #