[백준 14267] 회사 문화 1 (C++)

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

문제

---

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,

입력

---

첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)

사장은 상사가 없으므로 칭찬을 받지 않는다.

 

출력

---

1번부터 n번의 직원까지 칭찬을 받은 정도를 출력하시오.

 

 

문제 풀이

---

그래프 탐색 + dp 문제.

 

모든 칭찬을 입력받고 나서 한번에 탐색하는 방식으로 구현한다. 한 직원이 여러 번 칭찬을 받을 수 있으므로 map을 이용하여 칭찬받은 직원과 총 칭찬을 받은 정도를 저장해준다. 이후 dfs 탐색을 통해 전체 직원의 칭찬 받은 정도를 저장해준다.

 

한 직원이 칭찬받으면 그 사람의 모든 아랫 직원도 그만큼 칭찬받는다. 따라서 한 사람의 칭찬 정도가 a라면, 그 직원의 직속 부하는 칭찬 받은 것이 없다면 a이고, 아니라면 a + 해당 직원이 칭찬 받은 정도가 된다. 이를 이용해 사장부터 아랫 직원을 탐색하며 처음 탐색하게 된 아랫직원이 있다면 직속 상사의 칭찬 받은 정도를 가져와 직원의 칭찬 받은 정도를 구해주면 된다. map에 저장된 해당 직원의 칭찬정보가 있다면 직속 상사의 칭찬 정도에 그만큼 더해주면 되고, 없다면 직속 상사의 칭찬 받은 정도가 해당 받은 정도가 된다.

 

아래는 코드.

#include <iostream>
#include <stack>
#include <vector>
#include <map>
using namespace std;
vector<int>* v;
map<int, int> compliments;
map<int, int>::iterator it;
bool* isVisited;
int* dp;

void dfs()
{
	stack<int> dfsStack;
	dfsStack.push(1);
	isVisited[1] = true;
	while (!dfsStack.empty())
	{
		int current = dfsStack.top();
		bool isAdjacent = false;
		for (int i = 0; i < v[current].size() && isAdjacent == false ; i++)
		{
			int nextPerson = v[current].at(i);
			if (isVisited[nextPerson] == false)
			{
				isVisited[nextPerson] = true;
				dfsStack.push(nextPerson);
				isAdjacent = true;
				dp[nextPerson] = dp[current];
				it = compliments.find(nextPerson);
				if (it != compliments.end())
				{
					dp[nextPerson] += it->second;
				}
			}
		}
		if (isAdjacent == false)
		{
			dfsStack.pop();
		}
	}
}

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

	int N, M, i, w;
	int num;
	cin >> N >> M;
	v = new vector<int>[N + 1];
	isVisited = new bool[N + 1];

	dp = new int[N+1];
	for (int i = 1; i <= N; i++)
	{
		cin >> num;
		dp[i] = 0;
		isVisited[i] = false;
		if (num == -1)
		{
			continue;
		}
		v[num].push_back(i);
	}
	for (int j = 0; j < M; j++)
	{
		cin >> i >> w;
		it = compliments.find(i);
		if (it == compliments.end())
		{
			compliments.insert({i, w});
		}
		else
		{
			it->second += w;
		}
	}
	dfs();
	for (int i = 1; i <= N; i++)
	{
		cout << dp[i] << " ";
	}
	return 0;
}