<Medium> Cheapest Flights Within K Stops (LeetCode : C#)

https://leetcode.com/problems/cheapest-flights-within-k-stops/

📕 문제 설명

n개의 연결된 도시가 주어지고 몇 가지 비행편 정보가 주어진다.
flights[i] = [0에서 출발, 1에 도착, 2 가격]

출발지, 목적지, k가 주어질 때 최대 k번 멈추면서 출발지에서 목적지로 가는 가장 저렴한 가격 반환하기 (만약 목적지로 갈 수 없다면 1 반환)

• Input
  도시 개수, 비행편 정보, 출발지 번호, 목적지 번호, 최대 멈출 수 있는 개수 (k)
• Output
  출발지에서 목적지로 가는 가장 저렴한 가격

예제

시도 1.

그래프 만들고 src에서 갈 수 있는 모든 path 확인하기 (시간 초과)
아 다익스트라인데 기억이 안나서 개념이랑 기본 구현좀 다시 보고 해야겠다..

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[][] graph = new int[n][];
        for (int i = 0; i < n; i++)
        {
            graph[i] = new int[n];
        }

        for (int i = 0; i < flights.Length; i++)
        {
            int currSrc = flights[i][0];
            int currDest = flights[i][1];
            int cost = flights[i][2];

            if (graph[currSrc][currDest] == 0 || graph[currSrc][currDest] > cost)
            {
                graph[currSrc][currDest] = cost; // src -> dest 할때 mincost로 갱신
            }
        }
        int cheapestCost = Int32.MaxValue;
        for (int i = 0; i < n; i++) // src부터 갈 수 있는 길 가기
        {
            if (graph[src][i] != 0)
            {
                int currPathCost = FindPathToDest(i, 1, graph[src][i]);
                cheapestCost = cheapestCost > currPathCost ? currPathCost : cheapestCost;
            }
        }

        if (cheapestCost == Int32.MaxValue) cheapestCost = -1;
        return cheapestCost;

        int FindPathToDest(int currSrc, int currStops, int totalCost)
        {
            if (currSrc == dst) return totalCost;
            if (currStops > k) return Int32.MaxValue;
            int minCost = Int32.MaxValue;
            for (int i = 0; i < n; i++)
            {
                if (graph[currSrc][i] != 0)
                {
                    int currPathCost = FindPathToDest(i, currStops + 1, totalCost + graph[currSrc][i]);
                    minCost = minCost > currPathCost ? currPathCost : minCost;
                }
            }

            return minCost;
        }
    }
}

풀이

다익스트라 풀이

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        var adj = new Dictionary<int, List<int[]>>(); // key : src, value : dest랑 cost 담은 list
        foreach (int[] i in flights) 
        {
            if (!adj.ContainsKey(i[0])) 
            {
                adj[i[0]] = new List<int[]>();
            }
            adj[i[0]].Add(new int[] { i[1], i[2] });
        }

        int[] stops = new int[n];
        Array.Fill(stops, int.MaxValue);
        // TElement, TPriority
        var pq = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => a[0] - b[0])); // dist를 우선순위 비교자로 설정
        
        int[] distance = new int[] { 0, src, 0 }; // {dist, srcNode, 여태까지 들린 stop 개수}
        pq.Enqueue(distance, distance);

        while (pq.Count > 0) 
        {
            int[] temp = pq.Dequeue();
            int dist = temp[0];
            int srcNode = temp[1];
            int numOfStops = temp[2];
            // numOfStops랑 비교하는 거는 더 짧은 거리로 갔는데 k에 걸려서 답이 될 수 없는 것 처리 위함
            if (numOfStops > stops[srcNode] || numOfStops > k + 1) continue; // 이미 더 짧은 거리 기준으로 들렸거나 or stop 개수 초과
            stops[srcNode] = numOfStops;
            if (srcNode == dst) return dist; // 목적지 도착 
            if (!adj.ContainsKey(srcNode)) continue; // 더이상 갈 수 없는 경우

            foreach (int[] stop in adj[srcNode]) // 가장 거리 짧은 곳 기준으로 pq에 넣기  
            {
                var newDistance = new int[] { dist + stop[1], stop[0], numOfStops + 1 };
                pq.Enqueue(newDistance, newDistance);
            }
        }
        return -1;        
    }
}

결과

풀이 2.

갈 수 있는 최대 stops에 초점 두고 푼 풀이다.

모든 것에 대해 가장 짧은 길로 가도록 갱신해두는 것인데 여기서 k번까지만 돌기 때문에 짧은 거리지만 k 때문에 못가는 케이스는 알아서 걸러진다. 그리고 가능한 케이스중 가장 짧은 cost로 갱신해서 최종적으로 넣어주는 식 (다익스트라에서는 최단으로 뽑히는 길로 쭉 갔다가 k에서 걸리면 그 다음거 하는 식이면 이 풀이는 k개 넘어가는 것 자체를 애초부터 보지 않기에 더 효율적이다)

public class Solution 
{
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k)   
    {
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[src] = 0;
        for (int i = 0; i <= k; i++)
        {
            int[] temp = dist.ToArray();
            foreach (int[] flight in flights)
            {
                if (dist[flight[0]] != int.MaxValue) // src가 갈 수 있는 곳이면
                {
                    temp[flight[1]] = Math.Min(temp[flight[1]], dist[flight[0]] + flight[2]); // 최소 거리로 갱신 
                }
            }
            dist = temp;
        }
        return dist[dst] == int.MaxValue ? -1 : dist[dst];
    }
}

결과 2.