뉴스 전하기

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

문제

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

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

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

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

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

예제 입력 1
3
-1 0 0
예제 출력 1
2
예제 입력 2
5
-1 0 0 2 2
예제 출력 2
3
예제 입력 3
5
-1 0 1 2 3
예제 출력 3
4
예제 입력 4
24
-1 0 0 1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 12 13 14 16 16 16
예제 출력 4
7

문제 풀이

처음 문제를 접근한 방식은 현재 직접적으로 연결된 노드 중 해당 노드의 직접적으로 연결되어 있는 자식 노드가 가장 많은 경우부터 그리디하게 DFS탐색을 하는 방식을 취했다.
해당 과정으로 소스 코드 구현 후 제출하였으나, WA(2%)였다.

WA / 자식 노드 수를 기준으로 그리디하게 DFS 탐색

void dfs(int x, int cnt) {
    int nowCnt = cnt;
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;

    visited[x] = nowCnt;

    for(int i = 0; i < call[x].size(); i++) {
        pq.push({call[call[x][i]].size(), call[x][i]});
    }

    while(!pq.empty()) {        
        dfs(pq.top().second, ++nowCnt);

        pq.pop();
    }
}

그 이후, 다시 문제 풀이 방법을 생각해보니, 트리의 깊이가 깊은 부분과 연결된 노드부터 그리디하게 접근해야할 것으로 보였다.
그 이유는, 노드가 깊으면 깊을수록 전화를 연결하는 횟수가 늘어나게 되는데, 해당 부분을 최소화하여야 할 것 같았기 때문이다.

각각 노드에서의 최하단 노드(정확한 명칭을 까먹었다.)까지의 깊이를 별도 배열의 저장하는 과정을 구현하고, 노드의 깊이가 깊을 경우, 우선적으로 전화하도록 구현하였다. 그런데, 또 WA(2%)를 받았다.

WA / 노드의 깊이를 그리디하게 DFS 탐색

int findDepth(int start, int cnt) {
    int result = cnt;
    
    // 더 이상 진입 불가, 종료 조건
    if(call[start].size() == 0) {
        return result;
    }

    for(int i = 0; i < call[start].size(); i++) {
        result = max(result, findDepth(call[start][i], cnt + 1));
    }

    return result;
}

void dfs(int x, int cnt) {
    int nowCnt = cnt;
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;

    visited[x] = nowCnt;

    for(int i = 0; i < call[x].size(); i++) {
        pq.push({depth[call[x][i]], call[x][i]});
    }

    while(!pq.empty()) {
        dfs(pq.top().second, ++nowCnt);

        pq.pop();
    }
}

마지막 풀이방법은 결국 해당 부하가 그 밑의 부하들에게 연락하는 모든 시간에 대한 계산을 한 상태에서 가장 오랫동안 연락해야 되는 경우부터 정렬하여 접근해야 하는 과정으로 구현하게 되었다.
해당 풀이를 구현하는 과정에서 모든 방문시간을 구현하면서, 이를 DFS로 구현하는 것에 굉장한 고생을 하고 다른 분들의 풀이로도 많은 도움을 받았다. 굉장히 까다로운 문제였다.
한 부하에게 전화를 하고 다음 부하에게 전화하게 되면 시간이 추가로 들게 된다는 것을 DFS 안에서 구현하는 것에서 굉장히 어려웠다.

아래의 2번 TC를 직접 그려가며 풀어본다면, 마지막 풀이 방법으로 접근할 수 있을 것이다.

참고 TC

1)
Input
10
-1 0 0 1 2 2 2 3 7 2

Output
5

2)
Input
23
-1 0 1 1 1 2 2 2 3 3 3 4 4 4 0 14 15 16 17 18 19 20 21

Output
9
(만약, 맨 처음 내가 시도했던 방식의 알고리즘을 구현하게 될 경우, Output은 10이 된다.)

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n;
vector<pair<int, int>> call[51];
int dfs(int x);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        if(input != -1) {
            call[input].push_back({0, i});
        }
    }

    cout << dfs(0) << endl;

    return 0;
}

int dfs(int x) {
    int cnt = 0;

    for(int i = 0; i < call[x].size(); i++) {
        call[x][i].first = 1 + dfs(call[x][i].second);
    }

    sort(call[x].begin(), call[x].end(), greater<pair<int, int>>());

    for(int i = 0; i < call[x].size(); i++) {
        cnt = max(cnt, call[x][i].first + i);
    }

    return cnt;
}

• 문제 출처 : https://www.acmicpc.net/problem/1135
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.