[DFS]BOJ 16437_양 구출 작전

문제 링크 : https://www.acmicpc.net/problem/16437

16437번: 양 구출 작전

DFS를 재귀 형태로 구현하면 쉽게 풀 수 있는 문제이다.

문제의 그래프를 인접 리스트 형내로 변환한 뒤,

한 노드에 들어올 수 있는 양의 수 = 모든 자식 노드들에 들어올 수 있는 양의 수 합

이라는 점을 이용하여 루트 노드(1번)의 최종 값을 구하면 된다.

 

양의 수가 음수가 될 수 없다는 것과 각 값 자료형에만 유의하면 쉽게 해결할 수 있다.

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
 
using namespace std;
int n;
long long value[123457];
vector<int> tree[123457];
 
long long dfs(int node) {
    long long retval = 0;
 
    for (int i = 0; i < tree[node].size(); i++) {
        retval += dfs(tree[node][i]);
    }
    retval += value[node];
    if (retval < 0) retval = 0;
 
    return retval;
}
 
void init() {
    char c;
    cin >> n;
 
    for (int i = 2; i <= n; i++) {
        int val, path;
        cin >> c >> val >> path;
        if (c == 'W') value[i] = -1 * val;
        else value[i] = val;
        tree[path].push_back(i);
    }
}
 
int main() {
    init();
    long long answer = dfs(1);
    printf("%lld\n", answer);
 
    return 0;
}