1135번 : 뉴스 전하기 [C++]

문제 링크

성공 여부(걸린 시간): 성공 (1시간 42분)

아이디어

이 문제는 단순히 N이 50임을 확인하고 어라? 완탐해야지~ 하고 풀면 시간초과에 맞딱드리도록 만들어 놓은 문제이다.

그래서 문제를 풀기전에 조건과 문제의 요구사항을 먼저 확실히 확인하고 넘어가도록 하자.

1. 모든 직원은 단 하나의 부모노드를 가진다. (자식노드는 여러개 존재 가능)
2. 민식이는 직간접적으로 유일한 최고 대장이다.
3. 전화를 통해 소식을 전하는데 전화는 1분 걸리며 한번에 한 통만 가능하다.

 

한번에 한 통만 가능하다는 것은 그냥 각 자식노드들로 내려가면서 단순히 최고깊이를 구하는 것이 아닌

자식노드들에게 순차적으로 어떻게 전화를 걸었는 지에 따라 다른 결과값이 나옴을 알려준다.

 

그래서 나는 DP를 활용하여 바텀-업 방식으로 풀어줘야 겠다고 생각했다.

풀어서 설명하자면 리프노드들부터 올라오며 현재 자신의 노드 이하의 노드들에게

전화를 전부 최소시간으로 모두 돌렸을때의 시간을 dp 배열에 저장해주고

그런 방식으로 계속해서 아래에서 위로 올라오면서 갱신해주는 방식이다.

 

여기서 주의할 점은 단순히 자식 노드들 중에 최대값 + 1로 갱신해주는 실수를 범하기 십상인데 (나도 그랬음)

그러면 안된다.

왜냐면 전화를 거는 순서에 따라 추가되는 초를 반영해주어야 하기 때문이다.

그래서 나는 자식노드들의 소요시간들을 임시벡터에 넣어주고 정렬한다음 

그 정렬값에다 순서에 해당하는 초를 추가해서 최대값을 구해서 갱신을 해주었다.

 

그럼 여기서 그냥 어차피 정렬하고 자시고 최댓값만 구하고

제일 마지막에 전화를 걸 최소값 + 자신을 제외한 형제노드들의 수로 비교해서

갱신해주면 안되냐고 생각할 수 있다. (나도 그랬다.)

 

그럼 안된다. 반례가 있다.

만약 민식이의 자식노드들이 1, 3, 4, 3이라는 값을 갖게 되었다고 했을때

단순 비교를 하면 최댓값인 4와 최소값 + 자신을 제외한 형제노드들의 수인 (1+3) 4가 나오게 된다.

하지만 최솟값은 5이다.

왜냐 4 3 3 1 순서로 전화를 걸때

4는 1등으로 걸어서 그대로

3은 2등으로 걸어서 3 + 1 = 4

3은 3등으로 걸었기에 3 + 2 = 5

1은 4등이니까 1 + 3 = 4

이렇게 값이 5가 나오는게 정답이다. 그러나 내가 처음에 했던 방식으로 했다면 4%에서 눈물흘리면서 반례를 찾게 된다.

 

다행히 이 방법에 대해서 운좋게 떠올릴 수 있었고

적용하여 풀어주었다.

풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<vector<int>> graph;
vector<int> dp;

int get_time(int cur) {
    //이미 방문했던 노드라면 바로 return
    if (dp[cur] != -1) {
        return dp[cur];
    }
    //방문해야하고 만약 리프노드라면 return 1
    if (graph[cur].size()==0) {
        dp[cur] = 1;
        return 1;
    }

    vector<int> children_time;
    for (int x: graph[cur]) {
        int x_time = get_time(x);
        children_time.push_back(x_time);
    }
    sort(children_time.begin(), children_time.end(), greater<>());

    int maximum = -1;
    for (int i = 0; i < children_time.size(); i++) {
        maximum = max(maximum, children_time[i] + i);
    }
    dp[cur] = maximum + 1;
    return dp[cur];
}

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

    cin >> N;
    graph.assign(N, vector<int>());
    dp.assign(N, -1);
    for (int i = 0; i < N; i++) {
        int parent;
        cin >> parent;
        if (i != 0) {
            graph[parent].push_back(i);
        }
    }
    cout << get_time(0)-1;
    return 0;
}