<Medium> Network Delay Time (LeetCode : C#)

https://leetcode.com/problems/network-delay-time/

📕 문제 설명

1~n까지 n개의 노드가 주어지고 times 정보가 주어진다. k번째 노드가 시그널을 전송하기 시작할때 모든 노드가 시그널을 받기 위해 걸리는 최소 시간 반환하기 (모든 노드가 시그널 못받으면 -1 반환)
times[i] = (u_i, v_i, w_i), source, target, time

• Input
  노드 개수 n, times 정보, signal 보낼 노드 k
• Output
  모든 노드가 시그널을 받기 위해 걸리는 최소 시간 (불가능한 경우 -1)

예제

풀이

다익스트라 문제로 우선순위큐 사용해서 최단 거리 구할 수 있도록 구현

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        
        List<(int node,int weight)>[] adjList = new List<(int node,int weight)>[n+1];

        for(int i = 0;i <= n; i++)
        {
            adjList[i] = new List<(int node, int weight)>();
        }

        foreach(var time in times)
        {
            adjList[time[0]].Add((time[1],time[2])); // 0 -> 1 로 가는데 2의 비용 
        }

        int t = 0;
        bool[] visited = new bool[n+1];
        PriorityQueue<int,int> pq = new PriorityQueue<int,int>(); // element, priority
        pq.Enqueue(k, 0); // 시작 노드 pq에 넣기 

        while(pq.Count > 0)
        {
            pq.TryDequeue(out int currNode, out int currWeight);
            if(visited[currNode]) continue;
            visited[currNode] = true;

            t = Math.Max(t, currWeight); // 현재 가는 길 weight와 여태까지의 최대 중 더 긴 것으로 변경 
            foreach(var a in adjList[currNode])
            {
                if(!visited[a.node])
                {
                    pq.Enqueue(a.node, currWeight + a.weight); 
                }
            }
        }

        return visited.Where(x => x).Count() == n ? t : -1; // 다 방문했으면 t, 못했으면 -1 반환
    }
}

결과