[백준/BOJ] 백준 16437번 : 양 구출 작전

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

16437번: 양 구출 작전

 

1번 섬이 루트가 되도록 트리를 만들고, 트리의 연결을 자식 노드에서 루트 노드 방향으로 연결한다. 그리고, 리프노드부터 시작하여 위상 정렬로 탐색하여, 1번 섬인 루트에 도달하는 양의 수를 구하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int n;
vector<int> bridge[130000];
int w_cnt[130000]; //해당 위치에 있는 늑대의 수
long long s_cnt[130000]; //해당 위치에 있는 양의 수
long long result = 0;
int maked[130000];
vector<int> adj[130000]; //자식노드에서 부모 노드로 연결되는 그래프를 만든다
int indegree[130000];

void make_adj(int here) {
	maked[here] = 1;

	for (int i = 0; i < bridge[here].size(); i++) {
		int there = bridge[here][i];

		if (maked[there] == 0) {
			make_adj(there);
			adj[there].push_back(here);
			indegree[here]++;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 2; i <= n; i++) {
		char t;
		int a, p;
		cin >> t >> a >> p;

		if (t == 'W') {
			w_cnt[i] = a;
		}

		else {
			s_cnt[i] = a;
		}

		bridge[i].push_back(p);
		bridge[p].push_back(i);
	}

	//1번 노드가 루트인 트리에서, 자식노드->부모노드로 연결되는 그래프를 만든다
	make_adj(1);

	queue<pair<int, long long>> q; //(노드 번호, 살아남은 양의 수)
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) { //리프노드일때
			if (w_cnt[i] > 0) {
				q.push(make_pair(i, 0));
			}
			else {
				q.push(make_pair(i, s_cnt[i]));
			}
		}
	}

	while (!q.empty()) {
		int here = q.front().first;
		long long here_s_cnt = q.front().second;
		q.pop();

		if (here == 1) { //루트 노드에 도달 했을때
			result = here_s_cnt;
			break;
		}

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];
			indegree[there]--;
			s_cnt[there] += here_s_cnt;

			if (indegree[there] == 0) {
				if (s_cnt[there] > w_cnt[there]) {
					q.push(make_pair(there, s_cnt[there] - w_cnt[there]));
				}
				else {
					q.push(make_pair(there, 0));
				}
			}
		}
	}

	cout << result;

	return 0;
}