[240501] 알고리즘 리부트 57일차 - 백준 14267 자바

[Part2-Chapter04-Clip04]

- 백준 14267 회사 문화 1

상사가 칭찬을 받으면 직속 부하를 연쇄적으로 칭찬하기 때문에 방향이 없는 그래프인 트리 구조를 활용하면 된다. 직속으로 타고 내려가다가 가장 말단 사원까지 점수를 더해줘야 하기 때문에 DFS 방식으로 점수를 더해주는 방식으로 구현한다. 먼저 입력값을 받아주는데 각 직원의 직속 상사를 입력할 때, 입력받는 순서인 인덱스가 '부하'이고 입력 받는 값이 '상사'이다. ArrayList를 원소로 가지는 배열을 생성해서 배열의 인덱스는 상사, 그 원소인 리스트는 연결된 부하로 값을 입력하면 트리 탐색이 가능한 형태가 된다. 이렇게 입력 받고 나면 칭찬을 순서대로 받아주면서 직속 부하들에게까지 점수를 입력하는데 이 때, 칭찬을 받을 때마다 아래로 전파하다보면 시간 초과가 발생한다. (최대 직원 수 십만, 최대 칭찬 수 십만, 편향 트리이고 높은 직원에게 칭찬할 경우 이중 반복문 수행하면 최악의 100억 연산)  이를 해결하기 위해서 주어지는 칭찬을 미리 더해놓고 트리 탐색은 단 1회 수행하여 모든 점수를 한 번에 더해주면 된다.

package BaekJoon.tree;

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BJ14267_1 {
    private static int n, m;
    private static int[] compliments;
    private static ArrayList[] struct;
    private static BufferedWriter bw;
    private static boolean[] visited;


    public static void main(String[] args) throws IOException {

        // 직원 수 n, 최초 칭찬 수 m 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 인접리스트 만들기
        struct = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) struct[i] = new ArrayList<Integer>();

        // 인덱스가 부하, 값이 상사인 형태임 -> 인접 리스트 채우기 
        st = new StringTokenizer(br.readLine());

        int root = -1;

        for (int i = 1; i <= n; i++) {
            int boss = Integer.parseInt(st.nextToken()); //상사

            if (boss == -1) root = i; 
            else struct[boss].add(i); //인덱스가 부하 
        }

        // 직원별 칭찬 점수 배열 만들고
        compliments = new int[n + 1];

        // 방문 배열 만들고
        visited = new boolean[n + 1];

        // m번 반복문 돌면서 칭찬 받은 점수 더해놓기
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            // 칭찬 받은 직원 (receiver) 칭찬 점수 더해주기
            int receiver = Integer.parseInt(st.nextToken());
            int score = Integer.parseInt(st.nextToken());

            compliments[receiver] += score;
        }

        //System.out.println(Arrays.toString(compliments));

        addScore(root);

        br.close();

        for (int i = 1; i <= n; i++) bw.write(compliments[i] + " ");

        bw.flush();
        bw.close();
    }

    private static void addScore(int curr) {
        //System.out.println("현재 직원: " + receiver + "현재 점수: " + score);
        visited[curr] = true;

        for (int i = 0; i < struct[curr].size(); i++) {
            int nextEmployee = (int) struct[curr].get(i);

            if (visited[nextEmployee]) continue;

            compliments[nextEmployee] += compliments[curr];

            addScore(nextEmployee);
        }
    }
}

- 시간 초과 코드

package BaekJoon.tree;

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BJ14267 {
    static int n, m;
    static int[] compliments;
    static ArrayList[] struct;
    static BufferedWriter bw;
    static boolean[] visited;


    public static void main(String[] args) throws IOException {

        // 직원 수 n, 최초 칭찬 수 m 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 인접리스트 만들기
        struct = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) struct[i] = new ArrayList<Integer>();

        // 인덱스가 부하, 값이 상사인 형태로 인접 리스트 채우기 -> 단 방향 가능하지 않을까
        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            int boss = Integer.parseInt(st.nextToken());

            if (boss != -1) struct[boss].add(i);
        }

        // 직원별 칭찬 점수 배열 만들고
        compliments = new int[n + 1];

        // m번 반복문 돌면서
        for (int i = 0; i < m; i++) {

            // 방문 배열 만들고
            visited = new boolean[n + 1];

            st = new StringTokenizer(br.readLine());

            // 칭찬 받은 직원 (receiver)과 그 아래 직원까지 칭찬 점수 더해주기
            int receiver = Integer.parseInt(st.nextToken());
            int score = Integer.parseInt(st.nextToken());

            addScore(receiver, score);
        }

        br.close();

        for (int i = 1; i <= n; i++) bw.write(compliments[i] + " ");

        bw.flush();
        bw.close();
    }

    private static void addScore(int receiver, int score) {
        //System.out.println("현재 직원: " + receiver + "현재 점수: " + score);
        visited[receiver] = true;
        compliments[receiver] += score;

        for (int i = 0; i < struct[receiver].size(); i++) {
            int nextEmployee = (int) struct[receiver].get(i);

            if (visited[nextEmployee]) continue;

            addScore(nextEmployee, score);
        } 
    }
}