[BOJ알고리즘, C++]#1135_뉴스 전하기, DFS

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. DFS

https://webddevys.tistory.com/291#%232.%20%ED%83%90%EC%83%89-1

[자료구조]#6_그래프

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로 시작 노드를 기점으로 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색하는 방법입니다. 일반적으로,  DFS는 재귀 호출 혹은 스택 자료구조를 활용하여 구현 가능합니다.

 

2. 자식 노드들 중 최고!

1. 현재 노드의 총 통화 시간은 각 자식 노드들 중 최대 통화 시간이며, 각 자식 노드들은 자신의 순서가 오기까지 앞에 먼저 통화한 자식 노드들만큼의 시간을 추가적으로 기다려야 합니다. DFS를 통해 루트 노드를 시작 정점으로 자식 노드들에 대하여 재귀 호출을 수행합니다.
2. 현재 노드는 재귀 호출을 통해 수집한 자식 노드들 통화 시간 정보를 오름차순 정렬하고, 각 자식 노드의 총 통화 시간에 인덱스 만큼(이전 자식 노드의 통화 시간만큼 기다린 시간)을 더해줍니다. 이때, 정렬 작업을 통해 가장 통화 시간이 오래 걸린 자식 노드부터 먼저 통화를 해주어야 '최소 값'을 찾을 수 있기 때문입니다.
3. 최종적으로 오래 걸린 통화 시간에 -1(0번 노드는 통화로 전달 받는 시간이 없기 때문에)해주어 결과 값을 반환해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/1135
*   @문제: 루트 노드로부터 각 자식 노드에 통화하는 시간은 1분이 소요되며, 모든 노드에게 통화가 완료된 시점의 최솟 값
*   @설명
        1. 먼저, 두 번째 자식 노드는 첫 번째 자식 노드의 통화가 끝난 시점으로 차례대로 +1 씩 대기 시간도 포함해줍니다.
        2. 그리고, 각 노드는 자식 노드들의 결과 값 중 '최대 값'을 찾아서 부모 노드에게 반환해줍니다.
        3. 이를 재귀적으로 수행하며, 최종적으로 모든 노드에게 뉴스가 전달되는 시간의 최대 값이 반환됩니다.
        4. 중요한 점, 단말 노드에선 res = 1로 반환하지만, 마지막 루트 노드에 뉴스가 전달되는 시간이 0이므로, 마지막 결과 값 반환 시 -1을 해줍니다.
*/


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

#define MAX 50

int N;
vector<int> graph[MAX];

int dfs(int node)
{
    vector<int> children;
    int res = 0;
    int size = graph[node].size()-1;
    for(const auto& next : graph[node])
    {
        children.push_back(dfs(next));
    }

    sort(begin(children), end(children));

    for(int i=0; i<(int)children.size(); ++i)
    {
        res = max(res, children[i] + size--);
    }

    return res+1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    // 트리 구성
    for(int i=0; i<N; ++i)
    {
        int parent;
        cin >> parent;
        
        if(parent != -1) graph[parent].push_back(i);
    }

    int ans = dfs(0);

    cout << ans-1;

    return 0;
}

 

---