[C/C++] 백준 14267번 - 회사 문화 1

✏️ 문제 링크

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

14267번: 회사 문화 1

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

1번이 사장이므로 트리에서 루트가 된다고 할 수 있으므로, 1번 노드에서 dfs를 탐색해서 트리를 구성해 줍니다.

당연히 부모 노드를 저장을 해야 합니다.

 

그런다음 칭찬을 받게 되는데 한 직원이 여러 번 칭찬을 받을 수 있다는 점을 주의해야 합니다.

처음에 저도 한 번만 받을 수 있는 줄 알고 그 방식으로 구현을 해서 틀렸는데 여러 번 받을 수 있다고 가정하고

푸니까 바로 ac를 받았습니다.

 

마지막으로 다시 1번 노드에서 dfs를 돌리면서 각 노드에 칭찬횟수를 저장합니다.

 

풀면서 느꼈던 점은 백준 15681번과 문제 유형이 거의 유사합니다.

https://pooreumjung.tistory.com/375

[C/C++] 백준 15681번 - 트리와 쿼리

 

✏️ 문제 코드

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

vector<vector<int>>graph;
vector<int>boss;
vector<long>praise;
int N, M;
void makeTree(int node);
void countPraise(int node);

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;

	graph.resize(N + 1);
	praise.resize(N + 1);
	boss.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		int b;
		cin >> b;
		if (b == -1)
			continue;
		else {
			graph[i].push_back(b);
			graph[b].push_back(i);
		}
	}
	
	makeTree(1);

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		praise[u] += v;
	}

	countPraise(1);

	for (int i = 1; i <= N; i++)
		cout << praise[i] << " ";
}

void makeTree(int node)
{
	for (int next : graph[node]) {
		if (boss[next] != 0 || boss[next] == -1)
			continue;
		boss[next] = node;
		makeTree(next);
	}
}

void countPraise(int node)
{
	for (int next : graph[node]) {
		if (next < node)
			continue;
		else {
			praise[next] += praise[node];
			countPraise(next);			
		}
	}
}