[파이썬] 백준 16437: 양 구출 작전 (골드3)

[파이썬] 백준 16437: 양 구출 작전 (골드3)

16437번: 양 구출 작전

---

문제

---

풀이

0. 방향성 생각

• DFS
• 자식노드 정보 받아서 부모노드 업데이트
• 양은 +, 늑대는 -로 생각하기
• 양-늑대 > 0=이면 그대로 리턴, 양-늑대 < 0이면 0 리턴 (남은 양 0)

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = int(input())
tree = [[] for _ in range(n+1)]
info = {i:0 for i in range(n+1)}
visit = [False]*(n+1)

for i in range(2,n+1):
    a,b,c = input().split()
    b,c = int(b),int(c)
    tree[i].append(c)
    tree[c].append(i)
    
    if a == 'S': info[i] += b
    else: info[i] -= b

• 양은 양수, 늑대는 음수로 받아주기.
• 중복 탐색 방지를 위해 visit[node] = False로 초기화

2. 함수 정의

def dfs(x):
    
    if visit[x]: return 0
    
    remain = info[x]
    visit[x] = True
    for nx in tree[x]:
        temp = dfs(nx)
        remain += max(temp,0)
    return remain

print(dfs(1))

• 현재 노드를 info[x]로 받고 자식 노드에서 받아온 dfs값과 0 중 큰 값을 remain에 더해주기

 

 

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = int(input())
tree = [[] for _ in range(n+1)]
info = {i:0 for i in range(n+1)}
visit = [False]*(n+1)

for i in range(2,n+1):
    a,b,c = input().split()
    b,c = int(b),int(c)
    tree[i].append(c)
    tree[c].append(i)
    
    if a == 'S': info[i] += b
    else: info[i] -= b

def dfs(x):
    
    if visit[x]: return 0
    
    remain = info[x]
    visit[x] = True
    for nx in tree[x]:
        temp = dfs(nx)
        remain += max(temp,0)
    return remain

print(dfs(1))

 

코멘트