백준 16437 양 구출 작전 풀이

문제

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

&Title
16437번 - 양 구출 작전

&Question
N개의 섬으로 이루어진 나라가 있습니다. 섬들은 1번 섬부터 
N번 섬까지 있습니다.1번 섬에는 구명보트만 있고 다른 섬에는 양들 
또는 늑대들이 살고 있습니다.늘어나는 늑대의 개체 수를 감당할 수 
없던 양들은 구명보트를 타고 늑대가 없는 나라로 이주하기로 했습니다.각 
섬에서 1번 섬으로 가는 경로는 유일하며 i번 섬에는 pi번 
섬으로 가는 다리가 있습니다. 양들은 1번 섬으로 가는 경로로 
이동하며 늑대들은 원래 있는 섬에서 움직이지 않고 섬으로 들어온 
양들을 잡아먹습니다. 늑대는 날렵하기 때문에 섬에 들어온 양을 항상 
잡을 수 있습니다. 그리고 늑대 한 마리는 최대 한 
마리의 양만 잡아먹습니다.얼마나 많은 양이 1번 섬에 도달할 수 
있을까요? 

&Input
첫 번째 줄에 섬의 개수 N (2 ≤ 
N ≤ 123,456) 이 주어집니다.두 번째 줄부터 N-1개에 줄에 
2번 섬부터 N번 섬까지 섬의 정보를 나타내는 ti, ai, 
pi (1 ≤ ai ≤ 109, 1 ≤ pi 
≤ N) 가 주어집니다.ti가 'W' 인 경우 i번 섬에 
늑대가 ai마리가 살고 있음을, ti가 'S'인 경우 i번 섬에 
양이 ai마리가 살고 있음을 의미합니다. pi는 i번째 섬에서 pi번 
섬으로 갈 수 있는 다리가 있음을 의미합니다. 

&Output
첫 번째 줄에 구출할 수 있는 양의 수를 
출력합니다. 

&Example
-input
4
S 100 3
W 50 1
S 10 1
-output
60
-input
7
S 100 1
S 100 1
W 100 1
S 1000 2
W 1000 2
S 900 6
-output
1200

요약

• 각섬에 정보가 주어진다 W,S이냐에 따라 늑대나 양이다.
• 각 섬에 동물 개수, 이어진 부모 섬의 번호가 주어진다.
• 양이 지나오는 경로에 늑대가 있을 경우 늑대는 최대 1마리의 양을 먹을 수 있음(늑대는 양 한마리 먹으면 만족하고 배불러서 잔다 zz)
• 1번섬으로 몇마리의 양이 살아남을 수 있는가?

접근

• 트리를 사용한다.
• 백트래킹을 통해 살아남을 수 있는 양의 개수를 넘겨받는다.

풀이

1. res의 범위가 양의 개수를 더하다보면 넘을 수 있기 때문에 long long으로 선언
2. 양인 경우 + 늑대인 경우 -로 해뒀기 때문에 바로 tree[cur].cnt를 할당해준다.
3. 리프노드인 경우 res만 반환한다.
4. 리프노드가 아닌 경우 자식섬에서 살아 남아 넘어온 양들을 더해준다.
5. 만약 res가 0보다 작으면 살아남은 양은 없다 0으로 해주자.

    long long dfs(int cur) {
        long long res;
        res = tree[cur].cnt;
        for (int next : tree[cur].next) {
            res += dfs(next);
        }
        if (res < 0LL)res = 0LL;
        return res;
    }
   

틀렸던 이유

• 문제를 잘못이해했었다. 양이 넘어올때 마다 양을 한마리 먹을 수 있는건줄 알아서 문지기가 통행비 걷는거마냥 양들이 지나갈때마다 학살해버렸다 ㅋㅋ

소스

사이클이 생겨서 문제가 될꺼라 생각했는데 생각해보면 트리구조는 사이클이 생기면 루트노드와 연결되지 않는 독립적인 친구가 되서 상관없었다.

#include <iostream>
#include <vector>
using namespace std;

struct island {
	int cnt;
	vector<int> next;
};

int n;
island tree[123457];

long long dfs(int cur) {
	long long res;
	res = tree[cur].cnt;
	for (int next : tree[cur].next) {
		res += dfs(next);
	}
	if (res < 0LL)res = 0LL;
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	char c;
	int a, p;
	for (int i = 2; i <= n; ++i) {
		cin >> c >> a >> p;
		tree[i].cnt = (c == 'W' ? -a : a);
		tree[p].next.push_back(i);
	}
	tree[1].cnt = 0;
	cout << dfs(1) << endl;
	return 0;
}