문제
회사 트리에서 직속 상사가 부하에게 칭찬하면 그 부하의 모든 하위 직원에게 칭찬이 전달된다. M번의 칭찬 후 각 직원이 받은 총 칭찬 값을 구하라.
입력
첫째 줄에 N, M, 둘째 줄에 각 직원의 상사 번호, 이후 M줄에 칭찬 대상과 값이 주어진다.
출력
1번부터 N번까지 각 직원이 받은 총 칭찬 값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 3 -1 1 2 3 4 2 2 3 4 5 6 | 0 2 6 10 16 |
풀이
DFS로 트리를 순회하며 부모의 칭찬 값을 자식에게 누적 전파한다.
- 각 칭찬을 해당 직원의 값에 직접 더한다
- DFS로 루트부터 트리를 순회하며, 부모의 누적 칭찬을 자식에게 전파한다
wv[nxt] += wv[idx]로 부모의 값을 자식에 합산한다
핵심 아이디어: 칭찬을 직접 받는 직원에게만 기록한 뒤, DFS 한 번으로 위에서 아래로 누적합을 전파하면 O(N+M)에 해결된다.
코드
package day549;
import java.io.*;
import java.util.*;
public class Day540BOJ14267회사문화1 {
static List<Integer>[] list;
static int[] wv;
public static void main(String[] args) throws Exception {
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);
}
}
}복잡도
- 시간: O(N + M)
- 공간: O(N)