2D 그리드 크기가 주어지면 n*n 여기서 각 셀은 해당 셀을 통과하는 데 드는 비용을 나타냅니다. 여기서 작업은 다음을 찾는 것입니다. 최소 비용 에서 이동하다 왼쪽 상단 셀을 오른쪽 하단 셀. 주어진 셀에서 우리는 이동할 수 있습니다 4방향 : 왼쪽 오른쪽 위 아래.
메모: 입력 행렬에는 음의 비용 순환이 존재하지 않는 것으로 가정됩니다.
파이썬은 바이트를 문자열로 변환합니다.
예:
입력: 그리드 = {{9 4 9 9}
{6 7 6 4}
{8 3 3 7}
{7 4 9 10}}
출력: 43
설명: 최소 비용 경로는 9 + 4 + 7 + 3 + 3 + 7 + 10입니다.
접근하다:
아이디어는 사용하는 것입니다 Dijkstra의 알고리즘 그리드를 통해 최소 비용 경로를 찾습니다. 이 접근 방식은 그리드를 각 셀이 노드인 그래프로 처리하며 알고리즘은 항상 가장 낮은 비용의 경로를 먼저 확장하여 오른쪽 하단 셀에 대한 가장 비용 효율적인 경로를 동적으로 탐색합니다.
단계별 접근 방식:
설정 메뉴 열기
- 항상 최소 비용 경로를 먼저 처리하고 왼쪽 상단 셀을 해당 경로로 푸시하려면 최소 힙을 사용하세요.
- 시작 셀의 비용을 그리드 값으로 설정하는 최대값으로 비용 행렬을 초기화합니다.
- 각 셀에 대해 4개의 인접 셀을 모두 확인하세요.
- 더 낮은 비용 경로가 발견되면 셀 비용을 업데이트하고 이를 힙으로 푸시합니다.
- 오른쪽 하단 셀에 도달하기 위한 최소 비용을 반환합니다.
다음은 위의 접근 방식을 구현한 것입니다.
C++// C++ program to find minimum Cost Path with // Left Right Bottom and Up moves allowed #include
// Java program to find minimum Cost Path with // Left Right Bottom and Up moves allowed import java.util.PriorityQueue; import java.util.Arrays; class GfG { // Function to check if cell is valid. static boolean isValidCell(int i int j int n) { return i >= 0 && i < n && j >= 0 && j < n; } static int minimumCostPath(int[][] grid) { int n = grid.length; // Min heap to implement Dijkstra PriorityQueue<int[]> pq = new PriorityQueue<>((a b) -> Integer.compare(a[0] b[0])); // 2D grid to store minimum cost // to reach every cell. int[][] cost = new int[n][n]; for (int[] row : cost) { Arrays.fill(row Integer.MAX_VALUE); } cost[0][0] = grid[0][0]; // Direction vector to move in 4 directions int[][] dir = {{-1 0} {1 0} {0 -1} {0 1}}; pq.offer(new int[]{grid[0][0] 0 0}); while (!pq.isEmpty()) { int[] top = pq.poll(); int c = top[0] i = top[1] j = top[2]; // Check for all 4 neighbouring cells. for (int[] d : dir) { int x = i + d[0]; int y = j + d[1]; // If cell is valid and cost to reach this cell // from current cell is less if (isValidCell(x y n) && cost[i][j] + grid[x][y] < cost[x][y]) { // Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y]; // Push the cell into heap. pq.offer(new int[]{cost[x][y] x y}); } } } // Return minimum cost to // reach bottom right cell. return cost[n - 1][n - 1]; } public static void main(String[] args) { int[][] grid = { {9 4 9 9} {6 7 6 4} {8 3 3 7} {7 4 9 10} }; System.out.println(minimumCostPath(grid)); } }
# Python program to find minimum Cost Path with # Left Right Bottom and Up moves allowed import heapq # Function to check if cell is valid. def isValidCell(i j n): return i >= 0 and i < n and j >= 0 and j < n def minimumCostPath(grid): n = len(grid) # Min heap to implement Dijkstra pq = [] # 2D grid to store minimum cost # to reach every cell. cost = [[float('inf')] * n for _ in range(n)] cost[0][0] = grid[0][0] # Direction vector to move in 4 directions dir = [[-1 0] [1 0] [0 -1] [0 1]] heapq.heappush(pq [grid[0][0] 0 0]) while pq: c i j = heapq.heappop(pq) # Check for all 4 neighbouring cells. for d in dir: x y = i + d[0] j + d[1] # If cell is valid and cost to reach this cell # from current cell is less if isValidCell(x y n) and cost[i][j] + grid[x][y] < cost[x][y]: # Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y] # Push the cell into heap. heapq.heappush(pq [cost[x][y] x y]) # Return minimum cost to # reach bottom right cell. return cost[n - 1][n - 1] if __name__ == '__main__': grid = [ [9 4 9 9] [6 7 6 4] [8 3 3 7] [7 4 9 10] ] print(minimumCostPath(grid))
// C# program to find minimum Cost Path with // Left Right Bottom and Up moves allowed using System; using System.Collections.Generic; class GfG { // Function to check if cell is valid. static bool isValidCell(int i int j int n) { return i >= 0 && i < n && j >= 0 && j < n; } static int minimumCostPath(int[][] grid) { int n = grid.Length; // Min heap to implement Dijkstra var pq = new SortedSet<(int cost int x int y)>(); // 2D grid to store minimum cost // to reach every cell. int[][] cost = new int[n][]; for (int i = 0; i < n; i++) { cost[i] = new int[n]; Array.Fill(cost[i] int.MaxValue); } cost[0][0] = grid[0][0]; // Direction vector to move in 4 directions int[][] dir = { new int[] {-1 0} new int[] {1 0} new int[] {0 -1} new int[] {0 1} }; pq.Add((grid[0][0] 0 0)); while (pq.Count > 0) { var top = pq.Min; pq.Remove(top); int i = top.x j = top.y; // Check for all 4 neighbouring cells. foreach (var d in dir) { int x = i + d[0]; int y = j + d[1]; // If cell is valid and cost to reach this cell // from current cell is less if (isValidCell(x y n) && cost[i][j] + grid[x][y] < cost[x][y]) { // Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y]; // Push the cell into heap. pq.Add((cost[x][y] x y)); } } } // Return minimum cost to // reach bottom right cell. return cost[n - 1][n - 1]; } static void Main(string[] args) { int[][] grid = new int[][] { new int[] {9 4 9 9} new int[] {6 7 6 4} new int[] {8 3 3 7} new int[] {7 4 9 10} }; Console.WriteLine(minimumCostPath(grid)); } }
// JavaScript program to find minimum Cost Path with // Left Right Bottom and Up moves allowed function comparator(a b) { if (a[0] > b[0]) return -1; if (a[0] < b[0]) return 1; return 0; } class PriorityQueue { constructor(compare) { this.heap = []; this.compare = compare; } enqueue(value) { this.heap.push(value); this.bubbleUp(); } bubbleUp() { let index = this.heap.length - 1; while (index > 0) { let element = this.heap[index] parentIndex = Math.floor((index - 1) / 2) parent = this.heap[parentIndex]; if (this.compare(element parent) < 0) break; this.heap[index] = parent; this.heap[parentIndex] = element; index = parentIndex; } } dequeue() { let max = this.heap[0]; let end = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = end; this.sinkDown(0); } return max; } sinkDown(index) { let left = 2 * index + 1 right = 2 * index + 2 largest = index; if ( left < this.heap.length && this.compare(this.heap[left] this.heap[largest]) > 0 ) { largest = left; } if ( right < this.heap.length && this.compare(this.heap[right] this.heap[largest]) > 0 ) { largest = right; } if (largest !== index) { [this.heap[largest] this.heap[index]] = [ this.heap[index] this.heap[largest] ]; this.sinkDown(largest); } } isEmpty() { return this.heap.length === 0; } } // Function to check if cell is valid. function isValidCell(i j n) { return i >= 0 && i < n && j >= 0 && j < n; } function minimumCostPath(grid) { let n = grid.length; // Min heap to implement Dijkstra const pq = new PriorityQueue(comparator) // 2D grid to store minimum cost // to reach every cell. let cost = Array.from({ length: n } () => Array(n).fill(Infinity)); cost[0][0] = grid[0][0]; // Direction vector to move in 4 directions let dir = [[-1 0] [1 0] [0 -1] [0 1]]; pq.enqueue([grid[0][0] 0 0]); while (!pq.isEmpty()) { let [c i j] = pq.dequeue(); // Check for all 4 neighbouring cells. for (let d of dir) { let x = i + d[0]; let y = j + d[1]; // If cell is valid and cost to reach this cell // from current cell is less if (isValidCell(x y n) && cost[i][j] + grid[x][y] < cost[x][y]) { // Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y]; // Push the cell into heap. pq.enqueue([cost[x][y] x y]); } } } // Return minimum cost to // reach bottom right cell. return cost[n - 1][n - 1]; } let grid = [ [9 4 9 9] [6 7 6 4] [8 3 3 7] [7 4 9 10] ]; console.log(minimumCostPath(grid));
산출
43
시간 복잡도: O(n^2 로그(n^2))
보조 공간: O(n^2 로그(n^2))
동적 프로그래밍을 사용할 수 없는 이유는 무엇입니까?
네 방향 모두로의 움직임을 허용하면 최적의 하부 구조 가정을 깨뜨리고 셀을 다시 방문할 수 있는 사이클이 생성되기 때문에 여기서 동적 프로그래밍은 실패합니다. 이는 특정 셀에서 해당 셀에 도달하는 데 드는 비용이 고정되지 않고 전체 경로에 따라 달라짐을 의미합니다.
관련 기사:
최소 비용 경로
퀴즈 만들기