[백준] 16437 양 구출 작전

 

이 문제는 트리의 깊이를 이용해서 풀 수 있다

제일낮은 깊이부터 깊이0까지 깊이를 한 단계씩 올라오며 

정점 N개를 봐주면 된다!

부모를 미리 찾아주고 부모가 양인지 늑대인지만 확인하면 

현재층에서 다음층의 결과를 쫙 구할 수 있다!

 

다 풀고 다른사람의 풀이를 보니 위상정렬로도 풀 수 있다

위상정렬은 생각못했는데 한번 다시 풀어봐야겠따 위상정렬로

 

+ 위에서 아래로 내려오면서 한번에 구할 수 있는데 

   제일 한심하게 제일 열심히 위아래위아래 했다 거의 EXID 굿;;

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
int n,low_depth;
vector<vector<int>> Graph,depth;
vector<pair<char,ll>> arr;
vector<int> p;
 
void make_depth(int now,int parent,int dep){
    p[now]=parent;
    depth[dep].push_back(now);
    low_depth=max(low_depth,dep);
    for(int i=0;i<Graph[now].size();i++){
        int next = Graph[now][i];
        if(next != parent) make_depth(next,now,dep+1);
    }
}
 
void solve(int dep){
    if(dep==0) return;
    for(int i=0;i<depth[dep].size();i++){
        int now = depth[dep][i];
        int parent = p[now];
        if (arr[now].first=='S'){
            if(arr[parent].first=='S') arr[parent].second+=arr[now].second;
            else {
                arr[parent].second-=arr[now].second;
                if(arr[parent].second<=0){
                    arr[parent].first='S';
                    arr[parent].second=-arr[parent].second;
                }
            }
        }
    }
    solve(dep-1);
}
 
 
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %d",&n);
    Graph.resize(n);
    arr.resize(n);
    depth.resize(n);
    p.resize(n);
    for(int i=1;i<n;i++){
        char c; ll cnt; int next;
        scanf(" %c %lld %d",&c,&cnt,&next);
        next--;
        Graph[i].push_back(next);
        Graph[next].push_back(i);
        arr[i]={c,cnt};
    }
    make_depth(0,-1,0);
    solve(low_depth);
    printf("%lld\n",arr[0].second);
}