99클럽 코테 스터디 12일차 TIL + 뉴스 전하기(백준)

오늘의 학습 키워드

   - 알고리즘

   - 정렬

   - 그리디

   - 트리

   - DP

공부한 내용 본인의 언어로 정리하기

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

예전에 스터디를 할 때 DP유형하는 주에 풀이를 봤었다.

다만 그 주에 면접이 있어 문제를 풀지는 못했는데, 다시 봐도 어려운 문제라고 생각된다.

 

혼자 시도했었지만, 해당 방식이 틀렸기에 다른 사람의 코드를 찾아봤다.

내가 시도했던 방법은 아래와 같다.

 

시도했던 방법

1. 루트 노드부터 자식 노드까지 각각의 노드의 자식들이 몇 개의 자식 노드를 가지고있는지를 dfs를 이용해 계산한다.

(현재 노드 기준 리프노드까지 모든 자식들의 숫자를 계산)

2. 루트 노드부터 리프 노드까지 가장 자식을 많이 가지고 있는 노드를 bfs를 이용해 탐색한다.

3. 노드가 깊어질 때 마다 해당 노드의 깊이를 뉴스 전하는 시간의 최대값으로 갱신한다.

완전히 틀린 아이디어였다.

 

다른 사람의 코드를 참고해 만든 방법

1. 자식 정보를 저장하는 클래스 생성

2. 루트 노드부터 dfs 방식으로 탐색

3. 만약 해당 노드가 리프 노드라면 1을 반환

3 - 1. 아니라면 자식 노드들을 전부 탐색하는데 걸리는 시간을 반환

4. 자식 노드들에 대해 dfs 탐색을 하고 반환했던 시간 + 1을 List에 저장

5. 자식 노드들이 반환한 값을 역방향 정렬

5 - 1. 역방향으로 정렬하는 이유는 가장 오래 걸리는 자식 노드부터 전화해야 가장 효율적이기 때문

5 - 2. 자식 노드 1개당 1시간씩 걸리므로 마지막 자식 노드는 현재 노드의 모든 자식 노드들의 수 + 마지막으로 정렬된 자식 노드가 걸리는 시간 만큼의 시간이 걸리게 됨

6. 정렬된 자식 노드들을 반복문으로 돌며 자식 노드가 걸린 시간 + 자식 노드에게 전화하기까지 걸린 시간을 이용해 최댓값을 갱신

7. 루트 노드의 경우 0시간부터 시작하므로 - 1

 

 

풀이는 다음과 같다.

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

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static class Node {
        
        int idx, parentIdx;
        ArrayList<Integer> child;
        Node(int idx, int parentIdx) {
            child = new ArrayList<>();
            this.idx = idx;
            this.parentIdx = parentIdx;
        }
    }

    static Node[] graph;
    static int n;

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

        n = Integer.parseInt(br.readLine());
        graph = new Node[n];

        st = new StringTokenizer(br.readLine());
        st.nextToken();

        graph[0] = new Node(0, -1);

        for (int i = 1; i < n; i++) {
            int parentIdx = Integer.parseInt(st.nextToken());
            graph[i] = new Node(i, parentIdx);
            graph[parentIdx].child.add(i);
        }

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

    static int dfs(int node) {

        if (graph[node].child.isEmpty()) {
            return 1;
        }

        ArrayList<Integer> childList = new ArrayList<>();

        for (int child : graph[node].child) {
            childList.add(dfs(child) + 1);
        }

        childList.sort(Collections.reverseOrder());

        int max = 0;
        int size = childList.size();
        for (int i = 0; i < size; i++) {
            max = Math.max(childList.get(i) + i, max);
        }
        return max;
    }
}

 내일 학습할 것은 무엇인지

내일은 삼성 기출 알고리즘 문제와 보던 운영체제 강의를 마무리할 예정이다