[백준] 1135번. 뉴스 전하기(JAVA)

문제

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

---

풀이(21분)

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

public class Main {

    // 자식 중에 가장 긴 것 + 자기 자식의 개수만큼 시간이 걸림
    // 즉, 최상단에서부터 재귀로 하위를 탐색하면 됨.
    static Map<Integer, List<Integer>> boss = new HashMap<>();
    static int[] dp;
    static int n;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        dp = new int[n];
        for(int i = 0; i < n; i++){
            boss.put(i, new ArrayList<>());
        }

        st = new StringTokenizer(br.readLine());
        st.nextToken();
        for(int i = 1; i < n; i++){
            int owner = Integer.parseInt(st.nextToken());
            boss.get(owner).add(i);
        }

        int time = dfs(0);

        System.out.println(time);

    }

    static int dfs(int start){
        if(dp[start] != 0){
            return dp[start];
        }

        List<Integer> list = new ArrayList<>(); // 자식에 대해 시간이 오래 걸리는 것을 담아두기 위한 리스트
        for(Integer i : boss.get(start)){
            list.add(dfs(i)); // dfs에 추가
        }
        Collections.sort(list, Collections.reverseOrder());
        int addTime = 1; // 자식까지 가는데의 소요 시간
        for(Integer i : list){
            dp[start] = Math.max(i+addTime, dp[start]);
            addTime++;
        }
        return dp[start];
    }
}

---

문제 풀이 전략

 

1. dp를 통해 탐색한 것에 대해 더 이상 탐색하지 않게 dfs를 진행한다.

2. 진행 과정에서 자식마다의 소요 시간을 구하고, 내림차순으로 정렬한 뒤 +1 씩 하며 최대 시간을 dp[i]로 정한다.

3. 이 과정을 모든 인덱스에 대해 진행한다.

4. 최종적으로 dp[0]이 출력된다.