1. 문제 소개

3651. Minimum Cost Path with Teleportations

2. 풀이

혼자 풀지 못해서 풀이를 참조했다.
시간복잡도는 $O((k+1) * m * n)$이다.

class Solution:                                                                 # LeetCode 제출 형식에 맞춘 Solution 클래스 정의
    def minCost(self, grid: List[List[int]], k: int) -> int:                    # 격자에서 텔레포트를 최대 k번 고려한 최소 비용을 반환하는 함수
        m, n = len(grid), len(grid[0])                                          # 격자의 행/열 크기를 m, n으로 저장
        d = defaultdict(list)                                                   # 값별로 좌표들을 모아둘 딕셔너리를 초기화
        for i in range(m):                                                      # 모든 행 인덱스 i를 순회
            for j in range(n):                                                  # 모든 열 인덱스 j를 순회
                d[grid[i][j]].append((i, j))                                    # grid 값별로 (i, j) 좌표를 리스트에 추가
        
        inf = float('inf')                                                      # 무한대 값(초기화/경계 처리용)을 설정
        dp = [[inf] * n for _ in range(m)]                                      # dp 배열을 inf로 초기화(도달 비용 미정 상태)
        dp[0][0] = 0                                                            # 시작점 (0,0)의 누적 비용을 0으로 설정
        def update():                                                           # 위/왼쪽 기반 경로로 dp를 한 번 완화하는 내부 함수 정의
            for i in range(m):                                                  # 모든 행 i를 순회하며 dp를 갱신
                for j in range(n):                                              # 모든 열 j를 순회하며 dp를 갱신
                    temp = grid[i][j] + min(                                    # 현재 칸 비용 + (위/왼쪽에서 오는 최소 비용)으로 후보 계산
                        dp[i-1][j] if i else inf,                               # 위에서 오는 비용(첫 행이면 불가능 처리)
                        dp[i][j-1] if j else inf                                # 왼쪽에서 오는 비용(첫 열이면 불가능 처리)
                    )                                                           # 두 후보 중 작은 값을 선택
                    if temp < dp[i][j]: dp[i][j] = temp                         # 후보가 더 작으면 dp[i][j]를 갱신
        update()                                                                 # 초기 상태에서 위/왼쪽 이동만으로 dp를 한 번 계산

        keys = sorted(d, reverse=True)                                          # 값 그룹을 내림차순으로 정렬(스위프 순서 고정)
        for _ in range(k):                                                      # 텔레포트 완화 과정을 최대 k번 반복
            dist = inf                                                          # 현재까지의 “상위(큰 값) 그룹들에서의 최소 dp”를 저장할 변수
            for key in keys:                                                    # 큰 값부터 작은 값으로 각 그룹 key를 순회
                for i, j in d[key]:                                             # 현재 값 그룹의 모든 좌표를 순회
                    if dp[i][j] < dist: dist = dp[i][j]                         # dist를 (현재까지) 최소 dp로 갱신
                for i, j in d[key]:                                             # 현재 값 그룹의 모든 좌표를 다시 순회
                    dp[i][j] = dist                                             # 그룹 내부 dp를 dist로 평탄화(텔레포트 효과 반영)
            update()                                                             # 텔레포트로 낮아진 dp를 위/왼쪽 경로로 다시 전파
        return dp[-1][-1]                                                       # 도착점 (m-1,n-1)의 최소 비용을 반환

3. 마무리

꾸준함이 중요하다.