99클럽 코테 스터디 12일차 TIL / [백준] 뉴스 전하기

오늘의 학습 키워드

---

그리디 알고리즘, dfs

문제

---

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

• 플랫폼: 백준
• 문제명: 뉴스 전하기
• 난이도: 골드 2

풀이

---

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

public class Main {

    static List<Integer>[] childNodes;

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

        for (int i = 0; i < n; i++) {
            childNodes[i] = new ArrayList<>();
            int parent = Integer.parseInt(st.nextToken());

            if (parent >= 0) {
                childNodes[parent].add(i);
            }
        }

        System.out.println(dfs(0));
    }

    public static int dfs(int nodeNum) {
        if (childNodes[nodeNum].isEmpty()) {
            return 0;
        }

        List<Integer> times = new ArrayList<>();

        for (Integer childNodeNum : childNodes[nodeNum]) {
            times.add(dfs(childNodeNum));
        }

        Collections.sort(times, Collections.reverseOrder());

        int maxTime = Integer.MIN_VALUE;

        for (int i = 0; i < times.size(); i++) {
            maxTime = Math.max(times.get(i) + i + 1, maxTime);
        }

        return maxTime;
    }
}

접근

• 최초 접근
  • 최소가 되는 경우는 서브 트리의 합이 가장 큰 노드를 택하여 그리디하게 알고리즘을 해결할 수 있을 것이라 판단했습니다.
  • 그러나, 오답 처리가 되었고 반례를 발견하게 되었습니다.
    • 만약 서브 트리의 크기가 같은데 depth가 다르다면? → depth가 더 큰 노드. 즉, 전파가 가장 오래 걸리는 노드를 우선적으로 택해야 최소 시간에 해결할 수 있었습니다.
• 정답 접근
  • 깊이 우선 탐색을 통해 전파가 가장 오래 걸리는 노드를 확인할 수 있습니다.

    List<Integer> times = new ArrayList<>();
    
    for (Integer childNodeNum : childNodes[nodeNum]) {
        times.add(dfs(childNodeNum));
    }

  • 전파가 가장 오래 걸리는 노드에게 우선적으로 전파시킵니다.

    Collections.sort(times, Collections.reverseOrder());
    
    int maxTime = Integer.MIN_VALUE;
    
    for (int i = 0; i < times.size(); i++) {
        maxTime = Math.max(times.get(i) + i + 1, maxTime);
    }

    • 이것이 최소 시간에 전파를 시키는 방법이므로, maxTime을 구하여 리턴합니다.

소요 시간

2시간 30분

회고

---

정답 코드까지 접근하는 데 굉장히 오래 걸린 문제였습니다. 특히, 내림차순 정렬 및 depth + 이전 자식 노드 전파 시간 + 자식 노드 전파 시간(=1)을 떠올리기 어려웠습니다.