[BOJ/백준][Gold3] 16437 : 양 구출 작전 (C++)

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

16437번: 양 구출 작전

 

 

[난이도] Gold3
[유형] DFS

[풀이]
tree 구조이므로 1부터 시작하는 dfs를 돌려주면서 각 노드의 양의 수만큼 더해주고, 늑대의 수만큼 빼주면
루트인 1에 몇마리의 양이 도착하는지 알 수 있습니다.
늑대+양이 음수가 될때는 0으로 초기화를 해주고, 자료형이 int 형을 넘어갈 수 있는점을 주의해야 합니다.

 

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
vector<int> adj[123457];
int N,cnt[123457];
ll dfs(int p,int n){
    ll sum=cnt[n];
    for(auto nxt : adj[n]){
        if(nxt!=p) sum+=dfs(n,nxt);
    }
    return sum < 0 ? 0 : sum;   
}
int main(){
    scanf("%d",&N);
    for(int i=2;i<=N;i++){
        char c;
        int a,p;
        scanf(" %c%d%d",&c,&a,&p);
        if(c=='W') a=-a; 
        adj[i].push_back(p);
        adj[p].push_back(i);
        cnt[i]=a;
    }
    printf("%lld",dfs(-1,1));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/16437.cpp