[백준] 양 구출 작전

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

16437번: 양 구출 작전

위상정렬 문제입니다. 단방향 그래프이면서 1번 섬으로 가는 경로가 각 섬에서 유일하므로 싸이클이 없음을 알 수 있으므로 위상정렬이 가능합니다. 위상정렬을 통하여 각 섬에 도달할 수 있는 양의 수가 양수이면 다음 노드로 양을 이주시키면 됩니다.

 

import sys
from collections import defaultdict, deque

sys.stdin = open("input.txt", "r")

SHEEP = 'S'
WOLF = 'W'

input = sys.stdin.readline

n = int(input())

in_node = [0] * (n + 1)

# 각 노드의 양의 수
# 늑대인 경우 음수
sheep = [0] * (n + 1)

graph = defaultdict(int)

for i in range(2, n + 1):
    animal, cnt, next_node = list(input().split())

    # 부모 노드를 저장
    graph[i] = int(next_node)

    in_node[int(next_node)] += 1
    # 늑대인 경우 음수를 저장
    # 양인 경우 양수를 저장
    if animal == WOLF:
        sheep[i] = -int(cnt)
    else:
        sheep[i] = int(cnt)


q = deque()

for i in range(2, n + 1):
    if in_node[i] == 0:
        q.append(i)

while q:
    cur = q.popleft()

    if cur == 1:
        break

    next_node = graph[cur]

    in_node[next_node] -= 1

    # 현재 노드까지 도달한 양의 수가 양수인 경우 이동시킨다.
    if sheep[cur] > 0:
        sheep[next_node] += sheep[cur]

    if in_node[next_node] == 0:
        q.append(next_node)

print(sheep[1])