[BOJ] 백준 14267 : 회사 문화 1 (java)

🧪 14267 회사 문화 1

---

난이도 : 🌟 골드 4
유형 : 동적 프로그래밍

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

 

📝 문제

---

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

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

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

 

입력

 

첫째 줄에는 회사의 직원 수 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. DFS로 값을 직접 더하면 시간초과가 발생하기 때문에 마지막에 dp를 활용해서 순회를 통해 넣어준다.

🧐 핵심 로직

---

1. 상사와 부하직원의 관계를 이중 리스트의 형태로 저장한다.
2. dp를 사용하지 않고 for문 내부에서 DFS로 직접 값을 더해준다면 시간초과가 발생하기 때문에 모든 값들 일단 넣어둔 후 마지막에 순회와 dp를 통해 값을 갱신시켜준다.

💻 최종 코드 (1560 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    public static int n, m;
    public static List<List<Integer>> parent;
    public static int[] dp;
    public static void main(String[] args) throws IOException {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        parent = new ArrayList<>();
        parent.add(new ArrayList<>());
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            parent.add(new ArrayList<>());
            int employee = Integer.parseInt(st.nextToken());

            if (employee != -1) {
                parent.get(employee).add(i);
            }
        }

        dp = new int[n + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int employee = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            dp[employee] += value;
        }

        dfs(1);

        for (int i = 1; i <= n; i++) {
            System.out.print(dp[i] + " ");
        }

        br.close();
    }

    private static void dfs(int idx) {

        for (int nextIdx : parent.get(idx)) {
            dp[nextIdx] += dp[idx];
            dfs(nextIdx);
        }
    }
}