🌀 초보자용 가이드 ‘Minimum Cost Path with Teleportations’ - LeetCode 3651 (C++, Python, JavaScript)

Source: Dev.to

번역을 진행하려면 번역하고자 하는 본문 텍스트를 제공해 주시겠어요? 현재 제공된 내용은 소스 링크뿐이라 번역할 텍스트가 없습니다. 텍스트를 알려주시면 한국어로 번역해 드리겠습니다.

Problem Overview

그리드를 탐색하는 것은 고전적인 코딩 문제이지만, 텔레포테이션을 추가하면 게임이 완전히 바뀝니다.
다음이 주어집니다:

• 각 셀에 비용이 들어 있는 m x n 크기의 2차원 그리드.
• 텔레포트할 수 있는 최대 횟수를 나타내는 정수 k.
• 두 가지 이동 규칙:
  1. 표준 이동 – 오른쪽 또는 아래쪽으로 이동하며, 목적지 셀의 값만큼 비용이 듭니다.
  2. 텔레포테이션 – 현재 셀의 값보다 **≤**인 모든 셀로 점프할 수 있으며, 비용은 0입니다.

Goal: 왼쪽 위 셀 (0,0)에서 오른쪽 아래 셀 (m‑1,n‑1)까지 이동하는 최소 총 비용을 계산하세요.

접근법

텔레포트 없는 표준 DP

텔레포트가 없으면 문제는 간단한 DP로 축소됩니다:

dp[i][j] = grid[i][j] + min(dp[i‑1][j], dp[i][j‑1])

텔레포트 도입

텔레포트는 비용이 들지 않기 때문에 강력하지만, 현재 셀의 값보다 크지 않은 셀만을 목표로 할 수 있으며, 최대 k번만 사용할 수 있습니다.

우리는 층(또는 “라운드”) 별로 텔레포트 사용 횟수에 따라 문제를 해결합니다:

1. 텔레포트 사용 횟수 t = 0 … k마다 모든 가능한 셀 값에 도달하는 가장 저렴한 비용을 유지합니다.
2. 접미 최소 배열 suf_min_f[value]는 값이 ≥ value인 셀 중 도달 비용이 가장 낮은 값을 저장합니다. 이를 통해 “값이 x인 셀로 텔레포트하는 것이 더 저렴한가?”를 O(1)에 답할 수 있습니다.
3. 그리드를 행‑단위로 스캔하면서 다음을 업데이트합니다:
   • standard_move – 왼쪽 또는 위쪽에서 오는 비용에 현재 셀 값을 더한 값.
   • teleport_move – suf_min_f[x] (값이 ≥ x인 도달 가능한 셀 중 가장 좋은 비용).
   • 이 두 값 중 최소가 현재 셀의 새로운 비용이 됩니다.
4. 특정 t에 대해 전체 그리드를 처리한 후, 다음 반복을 위해 suf_min_f를 다시 구축합니다.

알고리즘은 suf_min_f가 반복 사이에 변하지 않으면 조기에 종료됩니다.

복잡도

• 시간: O(k * m * n) – 각 층마다 그리드를 한 번씩 스캔합니다.
• 공간: O(mx + n) 여기서 mx는 셀 값의 최대값(접미 배열용)이며, 선형 DP 행을 추가로 사용합니다.

예시

grid = [[1,3,3],
        [2,5,4],
        [4,3,5]]
k = 2

1. (0,0)에서 비용 0으로 시작합니다.
2. 아래로 이동하여 (1,0) → 비용 2.
3. 오른쪽으로 이동하여 (1,1) → 비용 7.
4. (1,1) (값 5)에서 (2,2) (값 5)로 무료 텔레포트합니다.
5. 목적지에 도달했으며 총 비용은 7입니다.

답은 7입니다.

솔루션 구현

C++ (GNU‑C++17)

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();

        // Edge case: free teleport possible
        if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) return 0;

        int mx = 0;
        for (auto& row : grid)
            for (int v : row) mx = max(mx, v);

        const int INF = 2e9;
        vector<int> suf_min_f(mx + 2, INF);
        vector<int> f(n + 1, INF);

        for (int t = 0; t <= k; ++t) {
            vector<int> min_f(mx + 1, INF);
            vector<int> new_f(n + 1, INF);
            if (t == 0) new_f[1] = 0;   // start cost

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int x = grid[i][j];
                    int standard = min(new_f[j], new_f[j + 1]) + x;
                    if (i == 0 && j == 0 && t == 0) standard = 0;
                    new_f[j + 1] = min(standard, suf_min_f[x]);
                    min_f[x] = min(min_f[x], new_f[j + 1]);
                }
            }
            f = new_f;

            // rebuild suffix minima
            vector<int> new_suf(mx + 2, INF);
            for (int v = mx; v >= 0; --v)
                new_suf[v] = min(new_suf[v + 1], min_f[v]);

            if (suf_min_f == new_suf) break;
            suf_min_f.swap(new_suf);
        }
        return f[n];
    }
};

Python 3

class Solution:
    def minCost(self, grid: list[list[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        if k > 0 and grid[0][0] >= grid[m - 1][n - 1]:
            return 0

        mx = max(max(row) for row in grid)
        INF = float('inf')
        suf_min_f = [INF] * (mx + 2)
        f = [INF] * (n + 1)

        for t in range(k + 1):
            min_f = [INF] * (mx + 1)
            new_f = [INF] * (n + 1)
            if t == 0:
                new_f[1] = 0   # start cost

            for i in range(m):
                for j in range(n):
                    x = grid[i][j]
                    standard = min(new_f[j], new_f[j + 1]) + x
                    if i == 0 and j == 0 and t == 0:
                        standard = 0
                    new_f[j + 1] = min(standard, suf_min_f[x])
                    min_f[x] = min(min_f[x], new_f[j + 1])

            f = new_f

            # rebuild suffix minima
            new_suf = [INF] * (mx + 2)
            for v in range(mx, -1, -1):
                new_suf[v] = min(new_suf[v + 1], min_f[v])

            if suf_min_f == new_suf:
                break
            suf_min_f = new_suf

        return f[n]

JavaScript (Node.js)

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var minCost = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) return 0;

    let mx = 0;
    for (let row of grid)
        for (let v of row) mx = Math.max(mx, v);

    const INF = Number.MAX_SAFE_INTEGER;
    let sufMinF = new Array(mx + 2).fill(INF);
    let f = new Array(n + 1).fill(INF);

    for (let t = 0; t <= k; ++t) {
        const minF = new Array(mx + 1).fill(INF);
        const newF = new Array(n + 1).fill(INF);
        if (t === 0) newF[1] = 0;   // start cost

        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                const x = grid[i][j];
                const standard = Math.min(newF[j], newF[j + 1]) + x;
                const best = Math.min(standard, sufMinF[x]);
                newF[j + 1] = best;
                minF[x] = Math.min(minF[x], best);
            }
        }
        f = newF;

        // rebuild suffix minima
        const nextSuf = new Array(mx + 2).fill(INF);
        for (let v = mx; v >= 0; --v)
            nextSuf[v] = Math.min(nextSuf[v + 1], minF[v]);

        if (JSON.stringify(sufMinF) === JSON.stringify(nextSuf)) break;
        sufMinF = nextSuf;
    }
    return

f[n];
};

핵심 요점

• 상태 확장 (텔레포트 횟수 차원을 추가)으로 각 허용된 텔레포트마다 동일한 DP 로직을 재사용할 수 있습니다.
• 접미 최소값을 사용하면 “값이 ≥ x인 모든 셀 중 가장 저렴한 비용”에 대해 O(1) 조회가 가능합니다.
• 공간 최적화: 이전 텔레포트 횟수의 결과만 필요하므로 메모리 사용량을 선형으로 유지합니다.

이 패턴은 배달 드론이 (비용이 많이 드는) 지상 주행이나 고고도 패드 사이를 (무료이지만 제한된) 비행할 수 있는 실제 라우팅 문제 등에서 많이 나타납니다.