개요

백준 16437번: 양 구출 작전

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

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

접근방식

첫번째 접근 방식(시간 초과)

1. 각 섬의 정보를 저장하는 벡터, 각 노드의 연결 노드 정보를 담은 벡터,
   각 노드의 방문 여부를 저장한 벡터, 리프노드들을 저장한 벡터들을 선언해줬다.

   //각 노드의 정보담은 벡터 
   vector<info> islandInfo;
   //각 노드의 연결 정보 담은 벡터 
   vector<vector<int> > v;
   //각 노드의 방문여부 탐색 
   vector<bool> visited; 
   //리프노드 벡터 
   vector<int> leaves;

   각 섬의 정보는 구조체를 통해 저장하였다.

   struct info {
   	char wolfOrSheep;
   	int amount;
   	int parent;
   };

2. 그 후, 입력값을 다 받고 리프 노드들을 DFS방식의 FindLeaves함수로 다 찾아줬다.

   void FindLeaves(int Node) {
   	visited[Node] = true;
   	int childrenAmount = 0;
   	for (int elem : v[Node]) {
   		if (visited[elem]) continue;
   		childrenAmount++;
   		FindLeaves(elem);
   	}
   	if (childrenAmount == 0) leaves.push_back(Node);
   }
   

3. 리프노드들에서 부모값들을 거슬러 올라가며 양 값을 다 더해줬다.

   long long returnSheepRemaining(int Node) {
   	
   	long long curNode = Node,SheepRemaining=0;
   	while (curNode != 1) {
   		//양이라면
   		if (islandInfo[curNode].wolfOrSheep == 'S') {
   			//양갯수 더해줌
   			SheepRemaining += islandInfo[curNode].amount;
   			islandInfo[curNode].amount = 0;
   		}
   		//늑대면
   		else {
   			//양갯수가 늑대보다 많다면
   			if (SheepRemaining > islandInfo[curNode].amount) {
   				//늑대갯수 빼줌
   				SheepRemaining -= islandInfo[curNode].amount;
   				//늑대 갯수 제거
   				islandInfo[curNode].amount = 0;
   			}
   			//늑대가 더 많다면
   			else {
   				islandInfo[curNode].amount -= SheepRemaining;
   				SheepRemaining = 0;
   			}
   		}
   		//늑대가 평생 한번만 먹는다고 늑대갯수 0으로 만들면 안됨, 먹은수만큼만 ㅃ줘야함
   		//islandInfo[curNode].amount = 0;
   		curNode = islandInfo[curNode].parent;
   	}
   	return SheepRemaining;
   }
   

4. 일단 늑대가 최대 한마리 먹는다는 말을
   섬에 양들이 들어올때마다 최대 한마리 먹는다는 말로 알아들어서
   늑대 갯수를 감소 안시키고 계속 함수를 진행했더니 틀렸다.

   그 후엔 노드에 늑대가 있다면 남은 양의 갯수를
   늑대 갯수만큼 빼고 늑대갯수를 0으로 만들어 줬다가 틀렸다.
   -> 늑대갯수를 양 갯수만큼 빼줘야한다.

   하지만 위의 방식들로 고쳤으나 시간초과가 났다.

두번째 접근 방식

1. 검색해본 결과 DFS방식 함수로 바로 답을 낼 수 있다는 글을 읽고
   번뜩 떠올랐다.
   FindLeaves함수에서 리프에 도달한 다음 이전 단계 함수로 돌아가면서
   값들을 넘겨주는 재귀 방식으로 접근하면 바로 답을 구할 수 있기때문이다.

   //재귀를 통해 리프값부터 가져오기 시작함
   long long FindLeaves(int Node) {
   	long long sheepRemaining = 0;
   	visited[Node] = true;
   	for (int elem : v[Node]) {
   		if (visited[elem]) continue;
   		sheepRemaining+=FindLeaves(elem);
   	}
   	//이전단계로 돌아가기전
   	//해당 노드가 양이 있는 노드라면 
   	if (islandInfo[Node].wolfOrSheep == 'S') {
   		//sheepRemaining값에 양 값 저장해준 후,
   		sheepRemaining += islandInfo[Node].amount;
   		//해당 노드의 양 갯수를 0으로
   		islandInfo[Node].amount = 0;
   	}
   	//해당 노드가 늑대가 있는 노드라면
   	else {
   		//양갯수가 늑대보다 많다면
   		if (sheepRemaining > islandInfo[Node].amount) {
   			//sheepRemainig변수에서 늑대갯수 빼줌
   			sheepRemaining -= islandInfo[Node].amount;
   			//늑대 갯수 제거
   			islandInfo[Node].amount = 0;
   		}
   		//늑대가 더 많다면
   		else {
   			//해당 노드의 늑대 갯수에서 sheepRemaining값 만큼 빼줌
   			islandInfo[Node].amount -= sheepRemaining;
   			// 남은양갯수가 0이므로 sheepRemaining은 0
   			sheepRemaining = 0;
   		}
   	}
   	//sheepRemaining변수 return
   	return sheepRemaining;
   	
   }

   이러면 returnSheepRemaining함수를 사용하지 않아도 바로 답이 나온다.
   

전체 코드

#include<iostream>
#include<vector>
using namespace std;
struct info {
	char wolfOrSheep;
	//~10억
	int amount;
	int parent;
};
//각 노드의 정보담은 벡터 ~12만
vector<info> islandInfo;
//각 노드의 연결 정보 담은 벡터 ~12만 * 12만
vector<vector<int> > v;
//각 노드의 방문여부 탐색 ~12만
vector<bool> visited; 

void Input() {
	int N = 0, amount = 0,parent=0;
	char wOS='S';
	info tmpInfo;
	cin >> N;
	v.resize(N + 2);
	visited.resize(N + 2,false);
	islandInfo.resize(N + 2);
	for (int i = 2; i <= N; i++) {
		cin >> wOS>>amount>>parent;
		tmpInfo = { wOS,amount,parent};
		islandInfo[i]=tmpInfo;
		v[i].push_back(parent);
		v[parent].push_back(i);
	}
}
//재귀를 통해 리프값부터 가져오기 시작함
long long FindLeaves(int Node) {
	long long sheepRemaining = 0;
	visited[Node] = true;
	for (int elem : v[Node]) {
		if (visited[elem]) continue;
		sheepRemaining+=FindLeaves(elem);
	}
	//이전단계로 돌아가기전
	//해당 노드가 양이 있는 노드라면 
	if (islandInfo[Node].wolfOrSheep == 'S') {
		//sheepRemaining값에 양 값 저장해준 후,
		sheepRemaining += islandInfo[Node].amount;
		//해당 노드의 양 갯수를 0으로
		islandInfo[Node].amount = 0;
	}
	//해당 노드가 늑대가 있는 노드라면
	else {
		//양갯수가 늑대보다 많다면
		if (sheepRemaining > islandInfo[Node].amount) {
			//sheepRemainig변수에서 늑대갯수 빼줌
			sheepRemaining -= islandInfo[Node].amount;
			//늑대 갯수 제거
			islandInfo[Node].amount = 0;
		}
		//늑대가 더 많다면
		else {
			//해당 노드의 늑대 갯수에서 sheepRemaining값 만큼 빼줌
			islandInfo[Node].amount -= sheepRemaining;
			// 남은양갯수가 0이므로 sheepRemaining은 0
			sheepRemaining = 0;
		}
	}
	//sheepRemaining변수 return
	return sheepRemaining;
	
}
void Solution() {
	long long ans = 0;
	cout<<FindLeaves(1);
}

int main() {
	Input();
	Solution();
}

문풀후생

늑대가 최대 한마리 먹는다는 부분이 좀
애매했던 문제같다.
한번에 dfs방식으로 돌아오면서 root부분에 다 모여서 푸는 방식을
좀 바로바로 떠올리게 연습해야겠다.