[백준] 1135 - 뉴스 전하기 (Java)

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

 

트리 구조로 이루어진 조직도가 있을 때, 제일 높은 조직의 사람이 자신의 직속 부하들에게 한번에 한 명씩 전화를 돌리며 뉴스를 전파한다.

직속 부하들도 전화를 받은 뒤엔 자신의 직속 부하에게 한번에 한 명씩 전화를 돌리며 뉴스를 전파한다.

이때 모든 직원들에게 뉴스가 전파되는 최소 시간을 구하는 문제이다.

 

나는 트리디피와 그리디가 섞인..? 느낌으로 풀었다. (DP보다는 그리디에 가까운 것 같아서 기여할 때는 그리디로만 기여했다.)

 

문제 이해하기

전화를 그냥 돌리면 간선의 수 만큼 시간이 소요되지 않을까? 왜 최소 시간을 구하라고 한 것일까?

예제 입력 2번을 보면 알 수 있다.

 

상사가 1번과 2번 중 어떤 사람에게 먼저 전화를 돌리는지에 따라 전체 전파에 걸리는 시간이 달라진다.

만약 1번에 먼저 전화를 돌리면, 2번에 전화를 돌릴 때는 1분이 지나있을 것이고, 2번의 자식 노드들에게 전파하는데 걸리는 시간이 전체적으로 1분 지연될 것이다.

따라서 2번에 먼저 전화를 돌려놓고, 2번 내부적으로 전파가 되는 시간 동안 1번 노드에 전파하면 3분만에 모두에게 전파할 수 있다.

 

 

풀이

나는 사실 여기에서 풀이 아이디어가 바로 떠올렸다.

어떤 직원 밑에 있는 모든 직원에게 뉴스를 전파하는데 걸리는 시간을 계산해보자.

 

먼저 리프 노드라서 부하직원이 없는 경우, 전파하는데 걸리는 시간은 0이다.

이 부하직원은 자신의 상사에게 걸리는 시간 0을 리턴한다.

 

그 상사는 여러 명의 부하직원을 가질 수 있다.

하지만 부하직원 여럿에게 동시에 전화를 돌릴 수 없으므로 누구에게 먼저 전화를 돌릴지 결정해야 한다.

직관적으로 부하 전체에게 전파하는데 시간이 오래 걸리는 직속 부하에게 먼저 전화를 돌려야 한다.

(예제 2번에서 2번을 먼저 고르지 않으면 전체적으로 1분이 지연되는 점에서 이해할 수 있다.)

 

따라서 직속 부하 각각에 대해서 재귀적으로 전제 전파하는데 걸리는 시간을 알아오라고 시킨다음,

그 모든 시간을 정렬해서 시간이 오래걸리는 직원부터 전화를 돌려서 이 직원이 모든 직원에 대해서 전파하는데 걸리는 시간을 측정한다.

 

그 시간은 (부하직원이 전체에게 전파하는데 걸리는 시간 + 그 부하직원에게 전화를 걸기까지 걸린 시간) 으로 구하고, 이 값들 중 최댓값을 취하면 된다.

 

예를 들어 어떤 직원의 직속부하 3명에 대해 각 부하가 자신의 밑에 있는 전체 직원에게 전파하는데 걸리는 시간이 2, 2, 3 이라고 해보자.

 

그러면 이 값을 내림차순으로 정렬하고 (3, 2, 2)

시간이 오래걸리는 직원부터 차례대로 전화를 걸면 각 걸리는 시간은

(3 + 1, 2 + 2, 2 + 3) = (4, 4, 5)

 

이 중에 최댓값은 5 이므로 현재 직원이 자신의 모든 부하직원에게 뉴스를 전파하는 시간은 5이다.

 

이렇게 각각의 노드에 대해서 그 노드의 모든 부하직원에게 뉴스를 전파하는 시간을 계산하다보면 최종적으로 루트 노드의 뉴스 전파 시간을 알 수 있고 그것이 정답이 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static List<List<Integer>> graph = new ArrayList<>();
    static int[] nodes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n+1; i++) {
            graph.add(new ArrayList<>());
        }
        nodes = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        for (int node = 0; node < nodes.length; node++) {
            int parent = nodes[node];
            if (parent == -1) continue;
            graph.get(parent).add(node);
        }

        int answer = calculateTime(0);
        System.out.println(answer);
    }

    public static int calculateTime(int node) {
        int [] times = graph.get(node).stream().map(Main::calculateTime).mapToInt(Integer::intValue).sorted().toArray();
        for (int i = times.length; i > 0; i--) {
            times[times.length - i] += i;
        }
//        System.out.println(node);
//        System.out.println(Arrays.toString(times));
        return Arrays.stream(times).max().orElse(0);
    }
}