[BaekJoon] 1135 뉴스 전하기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static HashMap<Integer, ArrayList<Integer>> relation;
    static int[] times;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        times = new int[N];

        relation = new HashMap<>();
        for(int employee = 0; employee < N; employee++)
            relation.put(employee, new ArrayList<>());

        for(int employee = 0; employee < N; employee++) {
            int num = scanner.nextInt();
            if(num == -1) continue;
            relation.get(num).add(employee);
        }
    }

    static void solution() {
        System.out.println(calcMinTime(0));
    }

    static int calcMinTime(int employee) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for(int next : relation.get(employee)) {
            times[next] = calcMinTime(next);
            queue.offer(new int[] {next, times[next]});
        }

        int order = 0, max = 0;
        while(!queue.isEmpty()) 
            max = Math.max(max, queue.poll()[1] + (++order));

        return max;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 민식이에서부터 가장 말단 사원들까지 뉴스가 전해지는 데에 걸리는 시간들 중 가장 오래 걸리는 시간을 구하면 그 시간이 이 문제의 답이 될 것입니다.
  • 이 시간을 구할 때는 가장 말단 사원부터 시작하여 민식이에게까지 전파되는 경우로 생각하여 뉴스가 전파되는 시간들을 구합니다.
  • 즉, 각 사원의 각 직속 부하들에게 뉴스가 전파되는 시간을 말단 사원부터 시작하여 각각 구하고, 1분에 한 명의 직속 부하에게만 뉴스를 전파할 수 있기 때문에 그 중 시간이 오래 걸리는 직속 사원 순서대로 뉴스를 전파합니다.
  • 그 중 가장 큰 시간을 구하면 그 시간이 해당 사원에게까지 전파되는데 걸리는 시간이라고 생각하고 이러한 정보들을 이용하여 해당 사원의 직속 상사에게까지 전파되는 시간 또한 구해나갑니다.
  • 이렇게 구해나가다가 민식이에게까지 전파된 시간이 구해진다면, 그 값이 이 문제의 답이 됩니다.

• 각 사원간의 관계를 HashMap을 통해 나타내고 아래 작업들을 진행하며 모든 소식을 전하는데 걸리는 시간의 최솟값을 구합니다.
  • PriorityQueue를 하나 생성하는데, 이 안에는 사원에 대한 정보가 들어가고, 이 정보는 사원의 번호와 해당 사원까지 소식이 전파되는데 걸리는 시간을 의미합니다. PriorityQueue는 시간이 오래 걸리는 순으로 정렬되게 됩니다.
  • 현재 사원의 직속 부하들을 순회하며 재귀를 통해 각 직속 부하들까지 소식이 전파되는데 걸리는 시간을 얻고 이 정보를 PriorityQueue에 넣게 됩니다.
  • PriorityQueue가 빌 때까지 PriorityQueue에서 사원 정보를 하나씩 꺼내면서 해당 사원까지 소식이 전파되는 데에 걸리는 시간 + order를 구하고 이들 중 가장 큰 값을 구해 이 값을 반환하여 이후 상사가 해당 사원까지 소식이 전파되는데 걸리는 시간을 이용하여 해당 상사까지 소식이 전파되는데 걸리는 시간을 구하도록 합니다.
    • order는 소식을 전하는 순서를 의미하는데, 1분에 한 명의 사원에게 소식을 전할 수 있기 때문에 가장 시간이 오래 걸리는 사원부터 시작하여 시간 기준 내림차순으로 순서를 정하고 이를 통해 각 직속 부하까지 소식을 전하는데 걸리는 시간을 구합니다.