BOJ_1135_뉴스 전하기 (Java, C++)

[Gold II] 뉴스 전하기 - 1135

문제 링크

성능 요약

메모리: 14372 KB, 시간: 108 ms

분류

다이나믹 프로그래밍, 트리에서의 다이나믹 프로그래밍, 그리디 알고리즘, 정렬, 트리

제출 일자

2025년 1월 30일 21:35:53

문제 설명

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

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

입력

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

출력

첫째 줄에 모든 소식을 전하는데 걸리는 시간의 최솟값을 출력한다.

문제 풀이

일단 정답을 찾기 위해 maxDepth를 사용해야 하는줄 알았다. 하지만 1번부모에 30명의 자식이 있고 depth가 5인 경우 의미가 없었다. 즉, 가장 많은 자식을 가진 노드를 생각해야했다. 이후 각 분기마다 1초가 걸리므로 어떤 분기를 선택해야하는가도 중요했다. 이에, 시간이 많이 걸리는(자식이 가장 많은) 순으로 분기를 따라가는것을 최우선으로 했다.

그림에서 보면 두번째줄 1에 3, 4, 5의 자식이 있다. 이 자식들은 각각 2, 2, 3 의 시간이 걸린다. 그래서 우선순위를 1-5 분기를 1순위, 1-3 분기를 2순위, 1-4 분기를 3순위로 뒀다. 사실 같은 time이 걸리면 상관없다. 이후 우선순위 + 시간 을 계산하여 최댓값을 갱신한 뒤 부모에 넣어준다.

코드

Java 코드

package BOJ_1135_뉴스전하기;
        
/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, parent[], maxT, time[];
    static ArrayList<Integer> childList;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1135_뉴스전하기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        parent = new int[N];
        time = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            parent[i] = num;
        }

        // 자식부터 시간 업데이트
        for(int i=N-1; i>=0; i--){
            updateTime(i);
        }

        bw.write(String.valueOf(time[0]));
        bw.flush();
        bw.close();
        br.close();
    }

    private void updateTime(int num) {
        childList = new ArrayList<>();
        for(int i=0; i<N; i++){
            if(parent[i] == num) childList.add(time[i]);
        }

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

        maxT = 0;
        for(int order = 1; order<=childList.size(); order++){
            maxT = Math.max(maxT, order + childList.get(order-1));
        }
        time[num] = maxT;
    }
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int N;
vector<int> parent;
vector<int> childTime;
int maxT = 0;

void updateTime(int num) {
    vector<int> childList;
    for (int i = 0; i < N; i++) {
        if (parent[i] == num) childList.push_back(childTime[i]);
    }

    sort(ALL(childList), greater<int>());

    maxT = 0;
    for (int order = 1; order <= childList.size(); order++) {
        maxT = max(maxT, order + childList[order - 1]);
    }
    childTime[num] = maxT;
}

void solve() {
    cin >> N;
    parent.resize(N);
    childTime.resize(N);

    for (int i = 0; i < N; i++) {
        cin >> parent[i];
    }

    for (int i = N - 1; i >= 0; i--) {
        updateTime(i);
    }
    cout << childTime[0] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}