[백준] 회사 문화 1 - Gold 4

[jusung-c]

문제 링크

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

문제 조건

• 내리 칭찬 문화가 있다.
• 1~n 번까지의 직원이 있다.
• 직속 상사와 칭찬 정보가 주어졌을 때 각 직원이 받은 칭찬 수치를 구하라

---

아이디어

1번 사장에서 DFS를 하면서 각 사원이 받은 칭찬 수치를 더해주면 된다.

여기서 부모 정보를 단순히 배열로 저장하면 시간 초과가 난다. 최대 10^5개의 각 정점에서마다 부모 정보를 확인하기 위해 10^5개의 배열을 확인해야 하기 때문이다.

따라서 인접리스트를 통해 정점별로 자식 리스트를 가지도록 표현하면된다.

그런데 또 놓친 부분이 있다. 칭찬을 한 사람이 여러 번 받을 수 있다는 점이다. 문제를 읽고 전혀 생각하지 못했던 부분이다. 이런 히든 케이스까지 잘 생각할 수 있도록 해야겠다.

---

시간 복잡도

최대 10^5개의 정점과 최대 10^5개의 간선으로 시간 안 풀이가 가능하다.

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N, M;
    static ArrayList<Integer>[] adj;
    static int[] score;

    public static void init() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int parent = Integer.parseInt(st.nextToken());

            if (parent == -1) continue;

            adj[parent].add(i);
        }

        score = new int[N + 1];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            score[n] += s;
        }
    }

    private static void pro() throws IOException {
        bfs(1);

        for (int i = 1; i <= N; i++) {
            bw.write(score[i] + " ");
        }
    }

    private static void bfs(int x) {
        Queue<Integer> que = new LinkedList<>();
        que.add(x);
        score[x] += score[x - 1];

        while (!que.isEmpty()) {
            x = que.poll();

            for (int y : adj[x]) {
                score[y] += score[x];
                que.add(y);
            }
        }

    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}