[알고리즘] 13 - 네트워크 지연 시간

1. 개요

이 문제는 Djikstra의 최단 경로 알고리즘에 대한 이해가 필요합니다.

이 문제는 최소 힙에 대한 이해가 필요합니다.

문제는 인접 행렬에 대한 이해가 필요합니다.

BFS(Breadth-First-Search)에 대한 이해가 필요한 문제

2. 솔루션

알고리즘(Djisktra의 최단 경로)은 그리디 알고리즘이기 때문에 솔루션은 그리 복잡하지 않습니다.

이 문제에 접근하기 위해 고려할 수 있는 첫 번째 큰 힌트는 각 노드가 원하는 만큼 연결된 노드를 가질 수 있다는 것입니다. 따라서 각 노드에 몇 개의 노드가 연결되어 있는지 추적하기 위해 인접 행렬이 필요합니다. 각 노드는 도달하는 가중치(시간)가 다르기 때문에 각 노드는 쌍으로 2D 배열에 저장됩니다.

C++ 예제

// time will be given as => vector<vector<int>>& times;
vector<vector<pair<int, int>>> adj(n+1);
for(auto t : times)
{
     int source = t[0];
     int dest = t[1];
     int time = t[2];

     // From 'source', we can reach 'dest' consuming 'time'
     adj[source].push_back({time, dest});
}

또한 시작 노드 K가 있으므로 레벨 순서대로 노드를 스캔해야 합니다. 우리는 K에서 각 노드에 도달하는 데 걸리는 최단 시간을 찾는 데 관심이 있기 때문에 레벨 순서 스캔이 필요합니다. 이는 현재 노드에 연결된 모든 노드를 스캔하여 수행할 수 있습니다(레벨 순서). 그리고 레벨 순서 검색은 BFS를 구현하여 수행할 수 있습니다.

BFS는 대기열을 사용하여 구현됩니다. 그러나이 특정 문제에 대해서는 우선 순위 큐 (최소 힙)가 필요합니다. 우선 순위 대기열을 사용하는 이유는 무엇입니까? 알고리즘이 탐욕적이기 때문에 경과 시간이 가장 짧은 노드를 먼저 테스트하려고 합니다. 따라서 누적 시간이 가장 작은 노드가 우선 순위를 갖습니다.

또한 i번째 노드에 도달하는 데 걸린 이전 최소 누적 시간을 추적할 수 있는 배열이 필요합니다. 이것은 결과를 반환하는 데 사용됩니다.

C++ 예제

// There are going to be n number of nodes
// recvTimes[i] : Minimum time it takes to reach i from K
vector<int> recvTimes(n + 1, INT_MAX);

// K from K will take 0
recvTimes[k] = 0;

3. 전체 구현

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {

        // 0: weight
        // 1: destination
        vector<vector<pair<int, int>>> adj(n+1);

        for(auto t : times)
        {
            int source = t[0];
            int dest = t[1];
            int time = t[2];
            adj[source].push_back({time, dest});
        }

        // Keep track of minimum time of receiving signal from node k
        vector<int> recvTimes(n + 1, INT_MAX);
        recvTimes[k] = 0;

        // Minheap
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0,k});

        while(!pq.empty())
        {
            // Getting the current node (pair).
            int currNode = pq.top().second;
            int currTime = pq.top().first;
            pq.pop();

            // Skip if the pair cannot be an optimal solution
            if (currTime > recvTimes[currNode]) 
                continue;

            // Scan all attached nodes and push to pq if the item can be an optimal solution.
            // Don't forget to update the elapsed time.
            for(auto item : adj[currNode]){
                if(recvTimes[item.second] > currTime+item.first){
                    recvTimes[item.second] = currTime+item.first;
                    pq.push({currTime+item.first, item.second});
                }
            }

        }

        int result = INT_MIN;

        // Getting results
        for (int i = 1; i <= n; i++){
            result = max(recvTimes[i], result);
        }

        return (result==INT_MAX) ? -1 : result;
    }
};