[백준 19538] 양 구출 작전 (Gold 3)

문제

https://www.acmicpc.net/problem/16437

접근

트리의 기본 개념 + DFS 탐색으로 접근

1) 트리는 두 개의 노드간 반드시 하나의 경로만 가진다. 이를 tree라는 인접 리스트로 구현한다.
2) 트리에 원소를 넣어주면서 늑대와 양의 값을 animal이라는 딕셔너리에 저장한다. 이 때 늑대는 음수로 넣어준다.
3) 이후 dfs 탐색을 진행하는데, if not tree[n] 조건문으로 리프노드인지 판별할 수 있다. 리프노드일 시 값을 animal[n]을 반환하게 한다.
4) 늑대는 섬을 탈출할 수 없으므로 반환 값이 음수일 경우 값을 0으로 만들어준다.

Code

import sys
from collections import defaultdict

sys.setrecursionlimit(123458)


def dfs(n):
    global answer

    if not tree[n]:
        return animal[n]
    summ = 0
    for next_node in tree[n]:
        summ += max(dfs(next_node), 0)

    answer = summ + animal[n]
    return answer


n = int(sys.stdin.readline())

tree = defaultdict(list)
animal = defaultdict(int)
answer = 0
for i in range(2, n + 1):
    t, a, p = map(str, sys.stdin.readline().split())
    tree[int(p)].append(i)
    if t == "S":
        animal[i] = int(a)
    else:
        animal[i] = -int(a)
dfs(1)
print(answer)