BOJ 14267: 회사 문화 1

#BOJ 14267: 회사 문화 1

14267번: 회사 문화 1

#풀이

어떤 직원이 자기 상관에게 칭찬을 받으면 자기 아래에 있는 직원도 칭찬받는다.

 

그래서 읽자마자 DFS로 풀면 쉽게 해결 가능하다고 생각이 들었다.

 

그래서 직원들의 상관을 입력받고

 

직원들의 상하 관계를 인접리스트로 입력받았다 방향이 있는 간선이라 생각하고 상관->부하 이런 식으로 저장하였다.

 

평소에 vis배열을 방문표시로 사용하였지만 이번에는 칭찬의 정도를 저장하는 것으로 사용하였다. 

 

처음에는 칭찬을 받을 때 마다 DFS를 돌려서 구했는데 시간초과가 발생했다.

 

고민을 하던 중 어차피 계속 더해가면 상관 없는 것 같아서 

칭찬을 모두 입력받고 vis 배열에 저장하였다. 이 때 똑같은사람이 칭찬을 여러 번 받을 수 있으므로 꼭 += 을 사용해서 저장해야 한다.

 

그 이후 BFS를 한 번 거치면 시간초과가 일어나지 않는다.

 

처음에 했던 걸로 하면 O(NM) 이지만 후자는 O(N+M)이 된다!

 

#코드

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int n, m;
vector<int> adj[100001];
int boss[100001];
int vis[100001];
void dfs(){
	stack<int> s;
	s.push(1);
	while (!s.empty()) {
		int prv = s.top(); s.pop();
		for (auto nxt : adj[prv]) {
			vis[nxt] += vis[prv];
			s.push(nxt);
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> boss[i];
		if (boss[i] == -1) {
			continue;
		}
		adj[boss[i]].push_back(i);
	}
	for (int i = 0; i < m; i++) {
		int num, weight;
		cin >> num >> weight;
		vis[num] += weight;
	}

	dfs();

	for (int i = 1; i <= n; i++) {
		cout << vis[i] << " ";
	}

	cout << '\n';

	return 0;
}