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

문제

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

14267번: 회사 문화 1

---

문제 요약

상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬한다.

즉, 상사가 한 직속 부하를 칭찬하면, 그 부하의 모든 부하들이 칭찬을 받는다.

 

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

 

직원들의 직속 부하관계와, 칭찬 정보가 주어질 때, 각자 칭찬 받은 수치를 출력한다.

---

코드

#include <iostream>
#include <vector>

using namespace std;

#define MAX_N 100000

int n, m; // 직원 수, 칭찬 횟수
int a, w; // 공통 조상을 구할 노드

bool visited[MAX_N + 1];
int arr[MAX_N + 1];
vector<int> edges[MAX_N + 1];

void dfs(int x) {
	visited[x] = true;
	for (int i = 0; i < edges[x].size(); i++) {
		int y = edges[x][i];
		if (visited[y]) continue;	
		arr[y] += arr[x]; // 자신이 받은 칭찬 수치를 직속 부하에게 전달
		dfs(y);
	}
}

int main() {
	cin >> n >> m;

	// 직속 부하 관계 입력
	for (int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		edges[p].push_back(i); // 상사가 부하에게만 칭찬 가능하므로 단방향 간선 사용
	}

	// 칭찬 받은 부하와 수치 입력
	for (int i = 0; i < m; i++) {
		cin >> a >> w;
		arr[a] += w; // 칭찬 받은 수치 저장
	}
	
	// dfs 탐색
	dfs(1);

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

---

코드 설명

처음에는 칭찬을 받을 때마다 DFS를 진행하여, 부하들에게 칭찬 수치를 전달하는 방식의 코드를 짰지만, 시간 초과로 실패했다.

 

따라서 칭찬을 한 번에 다 받고, 한 번만 DFS를 도는 방식을 이용했다.

 

1. 직원들의 직속 부하 관계를 입력 받고 간선을 연결한다.

+ 상사가 부하에게만 칭찬할 수 있으므로 단방향 간선을 사용한다.

 

2. 칭찬 받은 부하와 칭찬 수치를 입력 받고, 배열 arr에 저장한다.

 

3. 사장(1번)부터 DFS를 진행하며 자신이 받은 칭찬 수치를 직속 부하에게 전달한다.

 

4. 각 직원들이 받은 칭찬 수치를 출력한ㄴ다.