[leetCode] 1376. Time Needed to Inform All Employees

https://leetcode.com/problems/time-needed-to-inform-all-employees/description/

Time Needed to Inform All Employees - LeetCode

 

이 문제는 모든 직원이 해당 긴급소식을 아는데 까지 걸리는 시간을 구하는 문제이다.

그럼 해당 긴급소식을 모두 알려면, 해당 조직표에서 가장 오래 시간이 걸리는 경로의 시간이 정답이 될 것이다.

해당 오래걸리는 경로까지 가야, 모든 조직의 직원들이 소식을 들을 수 있기 때문이다.

 

아래는 내 코드이다.

struct Node
{
    int id;
    vector<Node*> vec;
};

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) 
    {
        vector<Node*> nodes(n);
        for(int i=0; i<n; i++)
        {
            nodes[i] = new Node(i);
        }

        Node* root = nullptr;
        for(int i=0; i<n; i++)
        {
            int memberID = manager[i];
            if(memberID  == -1)
                root = nodes[i];
            else
            {
                nodes[memberID]->vec.push_back(nodes[i]);
            }
        }
        int totalTime = search(root, informTime);
        for(int i = 0; i < n; i++)
        {
            delete nodes[i]; 
        }

        return totalTime;

    }

    int search(Node* root, vector<int>& informTime)
    {
        int maxTime = 0;

        for(int i=0; i<root->vec.size(); i++)
        {
            maxTime = max(maxTime, search(root->vec[i], informTime));
        }

        return maxTime + informTime[root->id];
    }
};

 

해당 코드의 대한 전개 방식은, 먼저 해당 조직표에 대해 만들어져 있는 상태가 아니기 때문에, 트리를 직접 만들어 줘야 겠다고 생각했다. 그래서 vector를 이용한 가변 배열 트리를 이용해서 조직표에 대한 트리를 만들어 줬다.

 

그리고 이 트리를 기반으로, DFS를 탐색해서 가장 오래 걸리는 시간을 계산한 것이다. 

그럼 처음 보스에서 시작해서 그 아래 직원, 또 그 아래 말단 직원까지 쭉 내려가 해당 경로의 시간을 계산하여 다시 후위 순위 방식으로 보스로 돌아오게 된다. 그러면서 해당 경로상의 최댓값을 구하게 된다.