743. Network Delay Time
풀이
다익스트라를 사용하여, 출발노드(k)에서 모든 노드로가는 최소값을 구하는 문제이다. 각 노드로 가는 최소값을 dp에 저장하고, 이 중에서 가장 큰 값이 가장 오래걸리는 시간이 될것이다.
1. times 인풋이 2d array주어지기 때문에, map 형태로 변환해준다.
{
출발지: [[목적지, time]],
출발지: [[목적지, time]],
...
}이런 자료구조가 되게 만들어준다.
2. queue에 [출발지,0]을 넣고 시작한다.
이 때, 출발지에 이어진 모든 노드들까지 가는 최소비용을 dp에 갱신한다.
그리고 visited아닌 애들만 queue에 넣는다.
중요한 점은 다익스트라를 구현하기 위해, 우선순위 큐를 사용하거나 minHeap을 사용하거나 하면되는데 자바스크립트에는 둘다없다...
그래서 따로 구현해주어야 하는데, 난 (귀찮아서) 구현하는 대신 큐에 있는 애들을 sorting 하면서 진행해주었다.
이 부분때문에 전형적인 다익스트라 시간복잡도와 차이가 생긴다. 이부분은 밑에서 또 설명함.
3. queue에서 하나씩 빼면서 방문했는지 확인한다.
다익스트라는 한번 방문한 노드는 다시 방문하지 않느다.
따라서, 이미 방문했으면 continue 처리하고 방문안한 노드가 나오면 방문처리를 한 후, 이어져있는 edge를 보며 최소비용을 dp에 갱신을 반복한다.
Time, Space Complexity
N: number of Nodes
E: number of Edges
연결되어있는 모든 간선을 확인하며 큐에 넣어주기 때문에 큐에 들어가는 최대개수는 E개가 된다.
따라서 O(E)만큼 반복하면서, 큐에 push, shift를 진행한다.
전형적인 다익스트라라면 우선순위 큐에 push, shift하는데에 드는 시간복잡도가 각각 O(logE)가 될 것이다. 하지만 난 우선순위 큐를 구현하지 않고 sorting으로 진행했기 때문에 O(ElogE)가 될 것이다.
그리고 정답로직에서 dp에 저장된 N개 배열 중 최댓값을 찾아야 하므로 O(N)가 소요된다.
따라서, 전형적인 다익스트라라면 time O(N + ElogE) 만큼 소요되겠지만, 내가 짠 코드는 time O(N + E * ElogE) 만큼 소요된다.
map에 사용되는 공간복잡도는 O(E), dp, visited는 O(N), 큐는 최대길이가 O(E)이므로 space O(N+E) 가 소요된다.
/**
* @param {number[][]} times
* @param {number} n
* @param {number} k
* @return {number}
*/
var networkDelayTime = function(times, n, k) {
const map = new Map();
const dp=Array(n+1).fill(Number.MAX_VALUE);
const visited = Array(n+1).fill(0);
dp[0]=0;
dp[k]=0;
for(let [now,next,time] of times){
if(map.has(now)) map.get(now).push([next,time]);
else map.set(now,[[next,time]]);
}
const q=[[k,0]];
while(q.length){
const [now, time]=q.shift();
if(visited[now]) continue;
visited[now]=1;
if(!map.has(now)) continue;
for(let [next,nextTime] of map.get(now)){
dp[next]=Math.min(dp[next], dp[now]+nextTime);
if(visited[next]) continue;
q.push([next,dp[next]]);
}
q.sort((a,b)=>a[1]-b[1]);
}
const max = Math.max(...dp);
return max===Number.MAX_VALUE ? -1 : max;
};자바스크립트에서 간단하게 우선순위 큐를 구현하는 코드를 추가해서 수정하겠음!
