[백준(python)] 16437번 : 양 구출 작전

1. 문제풀이

알고리즘 잘알 친구가 이 문제 풀 수 있으면 카카오 3-4번은 통과할 수 있는 문제라고 했다.
명성(?)과는 다르게 생각보다 막 까다롭지 않은 문제였음.
다만 python에서 재귀함수를 사용 중 런타임 에러(RecursionError)를 주의했어야 하는 문제다! -> 해결방법은 아래에..

문제를 이해하기 위해서 트리로 표현해보자.

그러면 위와 같은 그림을 그릴 수 있을 것이다.
(주의사항 : 모든 노드가 1과 무조건 이어져 있는 것이 아님. 나는 여기서 헤맸다.)

그리고 result값 계산을 이해하기 쉽게 트리로 그려보았다.

(섬의 순서대로 계산함)
그러면 결국 60이라는 값이 나올 것이다.

풀이 순서는 다음과 같다.

1. 트리 관계 나타내기
2. dfs를 이용하여 트리를 탐색하기
3. 노드의 타입이 W라면 result에서 빼준다. 단 뺀 값이 0보다 작을 경우에는 0이 된다.
4. 노드의 타입이 S라면 result에 더해준다.

풀이 코드는 다음과 같다.

# 0. 입력받기
import sys
sys.setrecursionlimit(123458)
input = sys.stdin.readline

N = int(input())
tree = [[] for _ in range(N+1)]
node = [[], [0,0]]

# 1. 트리구조 만들기
for i in range(N-1):
    kind, number, connection = input().split()
    tree[int(connection)].append(i+2)
    node.append([kind, int(number)])


# 2. dfs를 이용하여 탐색하기
def dfs(v): # v : 현재 노드
    result = 0 

    # 노드들을 탐색하며 더해준다.
    for i in tree[v]:
        result += dfs(i)

    # 노드의 타입이 늑대라면 빼준다.
    if node[v][0] == 'W':
        result -= node[v][1]
        if result < 0:
            result = 0
    # 노드의 타입이 양이라면 더해준다.
    else:
        result += node[v][1]
    return result

print(dfs(1))

2. 런타임 에러 (RecursionError)

문제 제출시 자꾸 런타임 에러가 난다면 반드시 해줘야 할 설정이 있다.

import sys
sys.setrecursionlimit(123458)

재귀 깊이를 설정할 수 있는 코드인데, 재귀함수를 사용할 때 필수적으로 적어줘야 하는 코드이다.

다 맞췄는데 안적어줘서 이렇게 많이 틀림😢