백준 | 14267번. 회사 문화 1 - DFS & DP 문풀

⬛ 백준 14267번. 회사 문화 1 - DFS & DP 문풀

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

14267번: 회사 문화 1

문제

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

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

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

입력

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

---

💚나의 풀이

1) 직속 상사 -> 직원의 관계를 '방향 그래프'로 표현

2) M개의 각 직원 i별 칭찬값 w 는 dy[i] = w 로서 초기화 해둔다.

 - 초기화값은 각 직원이 직전 상사에게 순수하게 받은 칭찬 w 값이 된다.

idx = 1	idx = 2	idx = 3	idx = 4	idx = 5
0	2	4	0	6

 

3) DFS(1) 호출 

-> 1이 반드시 사장이기 때문에 1부터 출발하면 된다.

-> 1부터 출발하면서 1의 다음 정점 nx를 꺼내어 dy[nx] += dy[cur]; 누적해준다.

            즉, 다음 nx직원의 dy[nx] 값 = 직전 cur 상사의 칭찬값을 누적시켜주는 방식으로 간다.

위의 dy[i]배열이 DFS() 이후 업데이트된 상태는 다음과 같다. 

- 기존에 갖던 값 + (직속 상사의 값 누적) 형태임

idx = 1	idx = 2	idx = 3	idx = 4	idx = 5
0	2 + (0)	4 + (2)	0 + (6)	6 + (6)

 

package to_1109_1;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int N, M;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] dy;// dy[i] : 직원 i가 직속상사에게 누적받은 칭찬값
	
	static void DFS(int idx) { //1로 시작
		for(int nx : graph.get(idx)) {
			dy[nx] += dy[idx];
			DFS(nx);//다음 깊이로 가라 
		}
	}

	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
	
		N = kb.nextInt();
		M = kb.nextInt();
		
		graph = new ArrayList<>();
		dy = new int[N+1];
		
		for(int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		
		//이제 직속 상사에 대한 값 저장
		//방향 그래프로서 저장.
		
		for(int i=1; i<=N; i++) {
			int val = kb.nextInt();
			if(val != -1) {
				graph.get(val).add(i);//val -> i(상사 val -> 직원 i)
			}
		}
		
		for(int i=0; i<M; i++) {
			//쿼리
			int a = kb.nextInt();//칭찬 받은 직원
			int v = kb.nextInt();//칭찬 값 
			
			dy[a] += v; //우선 기본값으로 칭찬값은 초기화 해두고 
		}
		
		DFS(1);
		for(int i=1; i<=N; i++) {
			System.out.print(dy[i] + " ");
		}
	}
}