[백준] 4315 - 나무 위의 구슬

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

4315번: 나무 위의 구슬

 

문제를 요약하면 어떤 정점들에 여러 개의 구슬이 있을 때, 적당히 배분하여 모든 정점에 구슬이 딱 1개만 존재하도록 하는 것이다.

이 문제의 핵심은 바로 "리프 노드부터 구슬을 채워나간다"는 것이다.

따라서 dfs로 리프노드부터 탐색해 부모 노드와 현재 노드의 구슬의 차이만큼 구슬의 상태를 변화하고, 이 차이의 절댓값만큼 답을 더해주면 된다.

 

사실 코드는 굉장히 간단하지만 리프 노드부터 채워나간다는 생각을 하기 어려웠던 문제인 것 같다.

 

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

vector<vector<int>> v;
int n, ball[10001], parent[10001];
long long ans;

void go(int node)
{
	for (auto &i : v[node])
	{
		go(i);
	}
	ball[parent[node]] += (ball[node] - 1);
	ans += abs(ball[node] - 1);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	while (cin >> n, n != 0)
	{
		v.clear();
		v.resize(n + 1);
		memset(ball, 0, sizeof(ball));
		memset(parent, 0, sizeof(parent));
		ans = 0;

		for (int i = 1; i <= n; i++)
		{
			int a;
			cin >> a;
			cin >> ball[i];
			cin >> a;
			for (int j = 0; j < a; j++)
			{
				int b;
				cin >> b;
				parent[b] = i;
				v[i].push_back(b);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			if (parent[i] == 0)
			{
				go(i);
			}
		}
		cout << ans << '\n';
	}
}