백준 18126 : 너구리 구구 (Python)

본문 링크

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

def DFS(Node,count):
    global total

    visit[Node]=True

    for i,j in Tree[Node]:
        if not visit[i]:
            total=max(total, count+j)
            DFS(i,count+j)
N=int(input())
Tree=[ [] for _ in range(N+1) ]

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

visit=[False]*(N+1)
total=0
DFS(1,0)

print(total)

📌 어떻게 접근할 것인가?

트리의 아주 기초적인 문제이다. 트리 처음공부할떄 풀면 좋은 문제라고 생각이 든다.

문제에서 트리와 가중치가 주어졌을때 가중치의 최대값을 구하는 것이다.

먼저 $Tree$ 를 입력받을때 양방향이기 때문에 2번 append 해주고 가중치도 같이 넣어준다.

이후 visit 배열을 통해 방문 처리를 해준다.
total 변수로 최대값을 저장한다.

$DFS$ 함수를 선언하고 그냥 모든 정점에 대해 탐색하면서 매번 total 값을 최대값으로 갱신해주면 된다.