[BOJ] 백준 14267번 회사 문화 1 (Java)

#14267 회사 문화 1

난이도 : 골드 4

유형 : 트리 DP / DFS

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번의 직원까지 칭찬을 받은 정도를 출력하시오.

 

문제 풀이  

전위 순회와 DP를 활용하여 풀이하는 트리 문제이다. 만약 DP를 사용하지 않고 모든 쿼리를 직접 DFS탐색으로 값을 부여한다면 시간초과가 발생한다. 그러므로 칭찬을 받은 모든 직원의 칭찬 수치를 한 번에 저장한 다음 단 한 번의 트리 순회를 통해 모든 값을 갱신해줘야 한다.

 

전위순회로 부모노드부터 자식노드로 값을 갱신해줘야 하는데 이유는 칭찬은 부하에게 연쇄적으로 내리 칭찬되기 때문이다. 만약 반대방향이었다면 후위순회로 자식노드부터 부모노드 방향으로 값을 갱신해주면 된다.

 

설계

1. 상관-부하 관계를 인접리스트 배열에 저장한다. list[b].add(a);
2. 칭찬 받은 모든 데이터를 배열에 저장한다. wv[man] += w;
3. 트리 전위순회를 통해 부모 노드부터 차례대로 값을 갱신해준다.  wv[nxt] += wv[idx];
4. 칭찬 수치가 저장된 배열을 출력한다.

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static List<Integer>[] list;
	static int[] wv;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		st = new StringTokenizer(br.readLine());
		for(int a=1; a<n+1; a++) {
			int b = Integer.parseInt(st.nextToken());
			if(b!=-1) {
				list[b].add(a);
			}
		}
		
		wv = new int[n+1];
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int man = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			wv[man] += w;
			
		}
		dfs(1);
		for(int i=1; i<n+1; i++) {
			System.out.print(wv[i]+" ");
		}
	}
	
	static void dfs(int idx) {
		for(int nxt : list[idx]) {
			wv[nxt] += wv[idx];
			dfs(nxt);
		}
	}
}