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

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

16437번: 양 구출 작전

🔔 문제 : 

 

어떤 나라는 1번 섬 부터 N개의 섬으로 이루어져 있습니다.

 

1번 섬을 제외한 각 섬에는 늑대나 양이 1 ≤ a ≤ 10^9 개 만큼 살고 있습니다.

 

각 섬들은 다른 섬에 이어지는 다리가 1개밖에 없으며, 이 섬들은 최종적으로는 1번섬으로 갈 수 있는 경로입니다.

 

각 양들이 1번섬으로 가고자 할 때, 살아남은 양들의 수를 찾아내는 문제 입니다.

 

단, 늑대는 평생동안 딱 양들을 한마리만 잡아 먹을 수 있습니다.

 

입력값으로는

첫 번째 줄에 섬의 개수 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번 섬으로 갈 수 있는 다리가 있음을 의미합니다.

 

예제입력

4
S 100 3
W 50 1
S 10 1

예제출력

60

---

🔔 Kick Point :

직접 트리를 만들고, DFS를 통하여 각 노드의 끝 노드부터 살아남은 양들을 리턴해주며 더해가면 되는 문제입니다.

 

여기서 중요한점은 DFS()를 돌 때 각 노드를 방문하는 횟수가 1번이여야 합니다. 즉 O(n)의 시간복잡도를 통하여 문제를 풀어야 합니다. 

 

DFS를 돌면서 양들의 개수를 리턴해줄 때,

늑대 일 때, 늑대의 값을 빼주고, 0이하일때는 return 값으로 0을 리턴해줍니다.

양 일 때는, return 값으로 현재 양들의 값을 더하여 리턴해줍니다.

 

또한 각 양들의 합이 int 범위를 넘어갈 수 있기에 long long int 크기를 사용합니다.

---

🔔 Code :

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

char animal[123457];
long long int animalCnt[123457];
vector<int> tree[123457];
int n;

long long int DFS(int n) {

	long long int cnt = 0;
	for (int i = 0; i < tree[n].size(); i++) {
		cnt += DFS(tree[n][i]);
	}

	if (animal[n] == 'W') {
		cnt -= animalCnt[n];
		if (cnt < 0) return 0;
		else return cnt;
	}
	else {
		return cnt + animalCnt[n];
	}
}


int main() {

	// Input
	cin >> n;
	for (int i = 2; i <= n; i++) {
		char c; cin >> c;
		int a, b; cin >> a >> b;
		
		animal[i] = c;
		animalCnt[i] = a;
		tree[b].push_back(i);
	}
	animal[1] = 'S';
	animalCnt[1] = 0;
	
	// Solve + Output
	cout << DFS(1);
}

---