[Python/파이썬] 백준 16437번: 양 구출 작전

문제

 

풀이

경로는 유일하므로 방문 처리는 따로 구현하지 않았다.

트리의 리프 노드까지 재귀를 통해 이동하고, 리턴 값을 통해 문제를 풀었다.

 

코드

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

n = int(input())
tree = [[] for _ in  range(n + 1)]

for i in range(2, n + 1):
    type, amount, root = input().split()
    amount, root = int(amount), int(root)
    if type == 'W':
        amount = -amount
    tree[root].append((i, amount))

def dfs(x, amount):
    for next, nextAmount in tree[x]:
        tmp = dfs(next, nextAmount)
        if tmp > 0:
            amount += tmp
    return amount

print(dfs(1, 0))

 

마무리

한번에 풀려서 조금 당황했다..ㅎㅎ