[백준 16437] 양 구출 작전 (C++)

16437번: 양 구출 작전

 

 

각 마을에 있는 늑대와 양의 수를 island 배열에 저장한다. 이때 늑대의 수는 음수로 저장하도록 했다.

양이 1번 섬으로 들어오는 최대 수를 알아야 한다. 따라서 1번 섬에서 시작해서 양을 데려온다는 생각으로 dfs를 수행했다.

 

1.

만약 현재 섬이 리프 노드이고 양이 살고 있다면 양을 데리고 올 수 있다.  return 양의 수

만약 현재 섬이 리프 노드이고 늑대가 살고 있다면 0을 리턴한다.

 

2.

현재 섬에 살고있는 양 또는 늑대(음수)를 현재 데려올 수 있는 양의 수에 더해준다.

그리고 현재 섬과 연결된 모든 섬에서 양을 데려와서 현재 양의 수에 더해준다.(늑대를 데려오는 경우(음수인 경우)는 0을 더해준다.)

 

3.

만약 현재 연결된 섬까지 데려온 양의 수가 음수라면 양들은 모두 늑대에게 먹혀 현재 섬을 통과할 수 없음을 의미한다.

따라서 0을 리턴한다.

양을 현재 섬까지 데려올 수 있다면 그 수를 리턴한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N;
ll ans;
vector<int> tree[123457];
ll island[123457];
 
void input(){
    cin >> N;
    char t;
    ll a;
    int p;
    for(int i = 2; i <= N; i++){
        cin >> t >> a >> p;
        tree[p].push_back(i);
        
        if(t == 'S') island[i] = a;
        else island[i] = -a;
    }
}
 
ll dfs(int now){
    if(tree[now].empty()){
        if(island[now] > 0) return island[now];
        else return 0;
    }
    
    ll sum = 0;
    sum += island[now];
    
    for(int i = 0; i < tree[now].size(); i++){
        int next = tree[now][i];
        sum += dfs(next);
    }
    
    if(sum < 0) return 0;
    return sum;
}
 
void solve(){
    ans = dfs(1);
    
    cout << ans << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}