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

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

14267번: 회사 문화 1

 

문제분석

분류

DP, 그래프, 트리, bfs-dfs, 트리에서의 DP

문제 설명

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

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

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

입력

첫째 줄에는 회사의 직원 수 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번의 직원까지 칭찬을 받은 정도를 출력하시오.

소스코드

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

vector<int> v[100001];
int good[100001] = { 0, };
int n, m, i, w;

void dfs(int num) {
	for (int i = 0; i < v[num].size(); i++) {
		good[v[num][i]] += good[num];
		dfs(v[num][i]);
	}
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		if (i == 1)continue;
		v[tmp].push_back(i);
	}
	for (int j =0; j < m; j++) {
		cin >> i >> w;
		good[i] += w;
	}
	dfs(1);

	for (int i = 1; i <= n; i++) {
		cout << good[i] << ' ';
	}
	return 0;
}

문제풀이

입력이 10만이므로 단순한 bfs로는 풀지 못한다.

그렇다면 어떻게 접근할까? -> 내리 칭찬이라는 단어가 DP와 비슷하게 들려왔다

• 칭찬의 양 w를 맨 앞부터 하나씩 더해주면 될 것 같다

1. 우선 인접리스트를 하나 선언한 뒤, 직원의 직속상사와 직원 본인의 order를 하나의 리스트가 되도록 입력받는다. 그러나 사장은 상사가 없으므로 과감하게 pass

ex) v[1][0] = 2(부장), v[2][0] = 3(차장), v[3][0] = 4(과장), v[4][0] = 5(대리)

2. 직원이 받는 칭찬의 양을 저장할 배열을 하나 선언 뒤, 입력받는다

3. dfs(1)을 실행한다 -> 왜 0부터 안하나면 사장은 상사가 없어서 pass 했기 때문

4. 어차피 v[num]의 size는 1이지만, dfs도 종료조건이 필요하므로 for문을 이용한다.

이 부분은 따로 종료조건을 설정해주어도 괜찮을 것 같다.

5. dfs(1)을 실행하면 v[1][0]은 2이므로, good[2] += good[1]( 2+= 0 )과 dfs(2)가 실행되고,

dfs(2)에서는 v[2][0] = 3이고 good[3] += good[2]( 4 += 2 )와 dfs(3)이 실행된다.

dfs(3)에서는 v[3][0] = 4이고 good[4] += good[3]( 0+= 6 )와 dfs(4)이 실행된다.

dfs(4)에서는 v[4][0] = 5이고 good[5] += good[4]( 6 += 6 )와 dfs(3)이 실행된다

6. 위처럼 앞 인덱스(=직속상사)가 가지고 있는 칭찬의 양이 계단식으로 더해져서 최종적으로는 good배열에 모든 직원의 칭찬의 양이 들어가게 된다.

---

https://github.com/oh2279/oh2279

GitHub - oh2279/oh2279

https://blog.naver.com/oh2279/222730620882

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