[백준 JAVA] 1135 : 뉴스 전하기

[백준 1135] 뉴스 전하기 : https://www.acmicpc.net/problem/1135

---

문제 조건 정리

 

1. 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다.
2. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다.
3. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다. -> 민식은 루트
4. 민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. -> 한 번에 한 사람씩! 순서가 중요함!
5. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다.
6. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다.
7. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작한다.

---

입력

 

1. 첫째 줄에 직원의 수 N이 주어진다.
2. 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어진다.
3. 0번 직원 (오민식)은 상사가 없기 때문에 -1이고, 나머지 직원 i의 상사 번호는 i보다 작거나 같은 음이 아닌 정수이다.
4. N은 50보다 작거나 같은 자연수이다.

입력이 상당히 깔끔하게 처리됨.

---

문제를 풀면서

 

1. 문제 설명이 직관적으로 와닿아서 이전에 풀었던 트리DP문제처럼 쉽게 해결할 수 있을 것으로 예상했지만 엄청 헤맸다......
   
   
2. 민식뿐만 아니라 자식을 갖는 모든 노드들은 그리디하게 전화 순서를 정해야한다!
   즉, 현재 노드를 기준으로 여러 서브트리 중, 뉴스의 전달이 가장 느리게 끝나는 노드에게 먼저 전화해야함 (그리디)
   그리고 그 서브트리들의 결과를 모아서 정렬한 후,
   
   뉴스의 전달에 가장 많은 시간이 소비되는 서브트리의 결과값 + 1 (첫번째로 전화함)
   그 다음으로 많은 시간이 소비되는 서브트리의 결과값 + 2 (두번째로 전화함)
   ...
   그 다음으로 많은 시간이 소비되는 서브트리의 결과값 + n (n번째로 전화함)
   
   이중에서 가장 큰 값을 찾아내는 과정을 DFS를 통해서 반복한다. 
   아래 그림과 디버깅 결과를 통해서 마지막 테스트 케이스를 이해를 할 수 있다!
3. /Users/making/Library/Java/JavaVirtualMachines/corretto-17.0.12/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=59587:/Applications/IntelliJ IDEA.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/making/IdeaProjects/ps/out/production/ps baekJoon.BJ1135
   24
   -1 0 0 1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 12 13 14 16 16 16
   노드 0에 대한 DFS 시작
       노드 1에 대한 DFS 시작
           노드 3에 대한 DFS 시작
               노드 8에 대한 DFS 시작
                   노드 17에 대한 DFS 시작
                   노드 17는 리프 노드입니다. 0을 반환합니다.
                   자식 노드 17에 대한 DFS 호출 결과: 0
                   자식 17 처리 중: time = 0, i = 0, maxTime = 1
               노드 8에서 반환: maxTime = 1
               자식 노드 8에 대한 DFS 호출 결과: 1
               노드 9에 대한 DFS 시작
               노드 9는 리프 노드입니다. 0을 반환합니다.
               자식 노드 9에 대한 DFS 호출 결과: 0
               자식 8 처리 중: time = 1, i = 0, maxTime = 2
               자식 9 처리 중: time = 0, i = 1, maxTime = 2
           노드 3에서 반환: maxTime = 2
           자식 노드 3에 대한 DFS 호출 결과: 2
           노드 4에 대한 DFS 시작
               노드 10에 대한 DFS 시작
               노드 10는 리프 노드입니다. 0을 반환합니다.
               자식 노드 10에 대한 DFS 호출 결과: 0
               노드 11에 대한 DFS 시작
               노드 11는 리프 노드입니다. 0을 반환합니다.
               자식 노드 11에 대한 DFS 호출 결과: 0
               자식 10 처리 중: time = 0, i = 0, maxTime = 1
               자식 11 처리 중: time = 0, i = 1, maxTime = 2
           노드 4에서 반환: maxTime = 2
           자식 노드 4에 대한 DFS 호출 결과: 2
           노드 5에 대한 DFS 시작
               노드 12에 대한 DFS 시작
                   노드 18에 대한 DFS 시작
                   노드 18는 리프 노드입니다. 0을 반환합니다.
                   자식 노드 18에 대한 DFS 호출 결과: 0
                   자식 18 처리 중: time = 0, i = 0, maxTime = 1
               노드 12에서 반환: maxTime = 1
               자식 노드 12에 대한 DFS 호출 결과: 1
               노드 13에 대한 DFS 시작
                   노드 19에 대한 DFS 시작
                   노드 19는 리프 노드입니다. 0을 반환합니다.
                   자식 노드 19에 대한 DFS 호출 결과: 0
                   자식 19 처리 중: time = 0, i = 0, maxTime = 1
               노드 13에서 반환: maxTime = 1
               자식 노드 13에 대한 DFS 호출 결과: 1
               자식 12 처리 중: time = 1, i = 0, maxTime = 2
               자식 13 처리 중: time = 1, i = 1, maxTime = 3
           노드 5에서 반환: maxTime = 3
           자식 노드 5에 대한 DFS 호출 결과: 3
           자식 3 처리 중: time = 3, i = 0, maxTime = 4
           자식 4 처리 중: time = 2, i = 1, maxTime = 4
           자식 5 처리 중: time = 2, i = 2, maxTime = 5
       노드 1에서 반환: maxTime = 5
       자식 노드 1에 대한 DFS 호출 결과: 5
       노드 2에 대한 DFS 시작
           노드 6에 대한 DFS 시작
               노드 14에 대한 DFS 시작
                   노드 20에 대한 DFS 시작
                   노드 20는 리프 노드입니다. 0을 반환합니다.
                   자식 노드 20에 대한 DFS 호출 결과: 0
                   자식 20 처리 중: time = 0, i = 0, maxTime = 1
               노드 14에서 반환: maxTime = 1
               자식 노드 14에 대한 DFS 호출 결과: 1
               자식 14 처리 중: time = 1, i = 0, maxTime = 2
           노드 6에서 반환: maxTime = 2
           자식 노드 6에 대한 DFS 호출 결과: 2
           노드 7에 대한 DFS 시작
               노드 15에 대한 DFS 시작
               노드 15는 리프 노드입니다. 0을 반환합니다.
               자식 노드 15에 대한 DFS 호출 결과: 0
               노드 16에 대한 DFS 시작
                   노드 21에 대한 DFS 시작
                   노드 21는 리프 노드입니다. 0을 반환합니다.
                   자식 노드 21에 대한 DFS 호출 결과: 0
                   노드 22에 대한 DFS 시작
                   노드 22는 리프 노드입니다. 0을 반환합니다.
                   자식 노드 22에 대한 DFS 호출 결과: 0
                   노드 23에 대한 DFS 시작
                   노드 23는 리프 노드입니다. 0을 반환합니다.
                   자식 노드 23에 대한 DFS 호출 결과: 0
                   자식 21 처리 중: time = 0, i = 0, maxTime = 1
                   자식 22 처리 중: time = 0, i = 1, maxTime = 2
                   자식 23 처리 중: time = 0, i = 2, maxTime = 3
               노드 16에서 반환: maxTime = 3
               자식 노드 16에 대한 DFS 호출 결과: 3
               자식 15 처리 중: time = 3, i = 0, maxTime = 4
               자식 16 처리 중: time = 0, i = 1, maxTime = 4
           노드 7에서 반환: maxTime = 4
           자식 노드 7에 대한 DFS 호출 결과: 4
           자식 6 처리 중: time = 4, i = 0, maxTime = 5
           자식 7 처리 중: time = 2, i = 1, maxTime = 5
       노드 2에서 반환: maxTime = 5
       자식 노드 2에 대한 DFS 호출 결과: 5
       자식 1 처리 중: time = 5, i = 0, maxTime = 6
       자식 2 처리 중: time = 5, i = 1, maxTime = 7
   노드 0에서 반환: maxTime = 7
   7
   
   Process finished with exit code 0
4.  

---

코드

 

package baekJoon;

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

public class BJ1135 {
    static List<List<Integer>> adjList;

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());

        adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
        for (int i = 0; i < n; i++) {
            int myParent = Integer.parseInt(stringTokenizer.nextToken());
            if (myParent == -1) continue;
            adjList.get(myParent).add(i);
        }

        // 가장 긴 시간을 소모하는 부하의 시간을 반환
        System.out.println(dfs(0));

    }

    private static int dfs(int parent) {
        List<Integer> children = adjList.get(parent);
        List<Integer> times = new ArrayList<>();

        // 리프 노드인 경우 0을 반환
        if (children.isEmpty()) {
            return 0;
        }

        // 모든 자식 노드에 대해 DFS를 수행하여 시간을 계산
        for (int child : children) {
            times.add(dfs(child));
        }

        // 내림차순으로 정렬하여 가장 오래 걸리는 순서대로 처리
        times.sort(Collections.reverseOrder());

        int maxTime = 0;
        // 각 자식 노드를 순서대로 처리하여 시간을 계산
        for (int i = 0; i < times.size(); i++) {
            maxTime = Math.max(maxTime, times.get(i) + i + 1);
        }

        return maxTime;
    }
}

 

---

문제를 풀고 난 후

 

전화의 순서를 그리디하게 처리해야한다는 것을 알았지만, 그걸 코드로 올바르게 구현하지 못해서 시간이 너무 많이 걸렸다.

다행히 문제에서 주어진 마지막 테스트 케이스가 상당히 복잡해서 그림을 그리며 힌트를 얻었다.

 

코드 자체는 간단하지만 정렬을 통해서 순서를 정하고, 그 순서에 맞게 부모노드가 전화하는데 걸리는 시간을 조합하여 그 중 최대값을 만들어낸다는 문제의 핵심 로직은 결코 단순하게 느껴지지 않았다 ㅠㅠ