[BOJ 16437] 양 구출 작전(Python)

문제

양 구출 작전

---

문제 해설

처음에 문제 이해가 잘 안되서 질문 목록을 찾아본 문제입니다. 양이 들어올때마다 늑대가 먹을 수 있는 것이 아닌, 늑대가 일생에 정해진 만큼 먹으면 더이상 먹지 못하는 구조입니다.

DFS로 풀 수 있는 문제이며, 제한 사항이 섬은 최대 123456개 까지 존재할 수 있습니다. 때문에 최악의 경우 한 줄기만 가지는 트리 구조가 형성될 수 있으므로 재귀 깊이를 123457까지는 늘려야 합니다.

1. 루트 노드(1번 섬)부터 자식 노드를 타고 내려오는 트리 구조를 만든다.
2. dfs로 다음 노드를 탐색한다. result에 현재 노드의 양의 수를 저장하고, 다음 노드를 탐색하면서 리턴되는 값들을 result에 더한다.
   만약 현재 노드가 늑대라면 result와 늑대 수를 비교 후 계산한다.
3. 리프 노드일 경우 양의 개체 수를 리턴한다.

---

풀이 코드

import sys

sys.setrecursionlimit(123458)
input = sys.stdin.readline
n = int(input())
connect = [[] for _ in range(n + 1)]
node = [[], [0, 0]]

for i in range(n - 1):
    spec, cnt, kid = map(str, input().rstrip().split())
    connect[int(kid)].append(i + 2)
    # node에 종류, 개체수 저장
    node.append([spec, int(cnt)])


def dfs(v):
    result = 0 if node[v][0] == "W" else node[v][1]
    # leaf 노드이고 양인 경우
    if len(connect[v]) == 0:
        if node[v][0] == "S":
            return node[v][1]
        else:
            return 0
    for x in connect[v]:
        result += dfs(x)
    # 늑대인 경우 밑 노드들을 탐색한 후 결과를 반영
    if node[v][0] == "W":
        # 양이 더 작을 경우
        if result < node[v][1]:
            node[v][1] -= result
            result = 0
        # 늑대가 더 작을 경우
        else:
            result -= node[v][1]
            node[v][1] = 0
    return result

print(dfs(1))

---