[백준][python]16437 양 구출 작전

문제

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

소스코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

if __name__ == "__main__":
    n = int(input())
    tree = [[] for _ in range(n+1)]
    node = [0] * (n+1)
    
    
    for i in range(2,n+1):
        a,b,c = input().split()
        tree[int(c)].append(i)
        if a == 'W':
            node[i] = -int(b)
        else:
            node[i] = int(b)
    
    def dfs(l):
        res = 0
        for i in tree[l]:
             res += dfs(i)
        res += node[l]
        if res < 0 :
            res = 0    
        return res      
    print(dfs(1))

설명

DFS 문제,  트리와 만들고 노드를 탐색하면서 개체수를 체크한다.

1번 node에 3번 노드와 4번 노드가 연결되어 있고 3번 노드와 2번 노드가 붙어있다.
그러면 트리를 구성하면 다음과 같다. 

tree[도착노드] = 출발 노드 
[[],[3,4],[],[2],[]]

이제 1 노드부터 탐색하면 3,4번을 탐색하게 되고 하위단에 2번 노드를 가장 먼저 탐색하게 되어 bottom - up 방식으로 내가 원하는대로 탐색할 수 있게된다.

 

그리고 노드는 그냥 node[1]이 첫번째 노드라고 생각하면 된다.

 

후기

1. 트리를 딕셔너리로 구현했더니 시간초과 발생

2. 자료구조를 배열로 변경해서 구현해도 시간초과 발생

3. 속도 빠르게 하는 조건 추가  (딕셔너리는 이거 해도 안됨)

- input 대신 sys.stdin.readline() 사용 하여 시간 단축

- 파이썬의 재귀 최대 깊이 기본 설정을 10**8 로 확장

input = sys.stdin.readline
sys.setrecursionlimit(10**8)