[백준 16437번] [분할 정복 / DFS] 양 구출 작전

Approach

사실 예제 입력 2에 대한 설명을 보고 가장 큰 아이디어를 얻었다.

문제에서 1번으로 가는 길은 유일하다는 표현을 통해 사이클이 없는 트리 구조임을 쉽게 파악할 수 있다. 따라서 점들의 관계를 표시해보면, 일종의 1번 노드를 루트 노트로 하는 트리로 이해할 수 있다.

 

그런데, 자식 노드를 기준으로 점차적으로 위로 올라오면서 양이 들어오는 양상이다. 

추가적으로 해당 점이 양이 있는 곳이라면 자식에서 올라오는 양의 수에 해당 점에 있는 양의 수를 더해주면 되고, 반대로 늑대가 있는 점이라면 자식에서 올라오는 양의 수에 해당 점에 있는 늑대의 수를 뺴주면 된다. (만약 음수가 나올 경우에는 0으로 만들어주면 된다.)

 

늑대는 이동하지 않는 상황이므로 dfs를 돌면서 양의 값을 ret으로 잡으면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

char state[123457];
vector<vector<int> > r;
bool visited[123457];
ll num_store[123457];

ll dfs(int x){
    visited[x] = 1;
    ll sheep_count = 0;
    for(int i = 0; i < r[x].size(); i++){
        int cur = r[x][i];
        if(!visited[cur]){
            sheep_count += dfs(cur);
        }
    }
    if(state[x] == 'S') return sheep_count + num_store[x];
    else return max(sheep_count - num_store[x], 0LL);
}

int main(void){
    memset(visited, 0, sizeof(visited));
    fastio;
    int n;
    cin >> n;
    r = vector<vector<int> > (n + 1);

    state[1] = 'S';
    num_store[1] = 0LL;

    for(int i = 2; i <= n; i++){
        char v;
        ll a;
        int index;
        cin >> v >> a >> index;

        r[i].push_back(index);
        r[index].push_back(i);
        num_store[i] = a;
        state[i] = v;
    }

    cout << dfs(1) << "\n";
    return 0;
}