[BOJ/백준] 16437 양 구출 작전

import sys
sys.setrecursionlimit(123456)
def dfs(node):
    if not graph[node]:
        if pet_list[node]>0:
            return pet_list[node]
        return 0 
    else:
        temp = 0
        for child_node in graph[node]:
            temp += dfs(child_node)
        temp += pet_list[node]
        if temp <0:
            temp = 0
        return temp

def input():
    return sys.stdin.readline().rstrip()
N = int(input())

graph = [[] for _ in range(N+1)]
pet_list = [0 for _ in range(N+1)]
for i in range(2,N+1):
    pet,*arg = input().split()
    pay,island = map(int,arg)
    if pet == 'S':
        pet_list[i] = pay
        graph[island].append(i)
    else:
        pet_list[i] = -pay
        graph[island].append(i)




print(dfs(1))

이 문제는 기본적인 트리 문제였다. 그래프의 경로와 각 양과 늑대를 양수와 음수로 각각 매칭을 했다.

 

그리고 재귀를 통해서 리프노드까지 간 뒤에 양수이면 양수를 음수이면 0을 보내줬다.

 

그리고 그렇게 return 된 값들을 전부 더한뒤에

 

현재 아일랜드의 값을 더해주고, 그 값이 0미만이 되면 0으로 보내주고 그게 아니면 원래대로 보내주면 풀리는 문제이다.

 

 

import sys
from collections import defaultdict,deque
def input():
    return sys.stdin.readline().rstrip()


N = int(input())

graph = defaultdict(list)
pet_list = [0 for _ in range(N+1)]
parents = [0 for _ in range(N+1)]
for next_node in range(2,N+1):
    pet,*arg = input().split()
    pay,island = map(int,arg)
    if pet == 'S':
        pet_list[next_node] = pay
    else:
        pet_list[next_node] = -pay
    graph[island].append(next_node)
    parents[next_node] = island

que = deque()
que.append(1)
stack = []
while que:
    cur_node = que.popleft()
    stack.append(cur_node)
    for next_node in graph[cur_node]:
        que.append(next_node)

while stack:
    cur_node = stack.pop()
    pet_list[parents[cur_node]] += max(0,pet_list[cur_node])

print(pet_list[0])

재귀를 이용하지 않고 푸는 방법이다.

 

먼저 bfs로 탐색하면서 그 순서를 stack에 넣어주고, 끝에서부터 하나씩 꺼내주면 된다.