1. 문제 소개

3650. Minimum Cost Path with Edge Reversals

2. 풀이

다익스트라를 사용한 방법이다.
시간복잡도는 $O((n + m) \text{log}\, n)$이다.

class Solution:                                                         # LeetCode 제출 형식에 맞춘 Solution 클래스 정의
    def minCost(self, n: int, edges: List[List[int]]) -> int:            # 0에서 n-1까지의 최소 비용을 반환하는 함수
        g = [[] for _ in range(n)]                                       # 각 노드의 인접 리스트를 담을 그래프 g를 초기화
        for x, y, w in edges:                                            # 주어진 간선 리스트를 순회하며
            g[x].append((y, w))                                          # 정방향 x->y 비용을 w로 추가
            g[y].append((x, 2 * w))                                      # 역방향 y->x 비용을 2*w로 추가하여 모델링

        dist = [inf] * n                                                 # 각 노드까지의 최단거리 배열을 무한대로 초기화
        visited = [False] * n                                            # 다익스트라 확정(방문) 여부를 저장할 배열 초기화
        dist[0] = 0                                                      # 시작 노드(0)의 거리를 0으로 설정
        heap = [(0, 0)]                                                  # (현재거리, 노드) 형태의 최소 힙을 시작점으로 초기화

        while heap:                                                      # 힙이 빌 때까지 최단거리 탐색 반복
            cur_dist, x = heapq.heappop(heap)                            # 힙에서 현재까지 비용이 가장 작은 노드를 꺼냄

            if x == n - 1:                                               # 목적지 노드에 도달하면
                return cur_dist                                          # 현재 거리가 최단이므로 즉시 반환

            if visited[x]:                                               # 이미 최단거리가 확정된 노드라면
                continue                                                 # 중복 처리를 피하기 위해 건너뜀
            visited[x] = True                                            # 현재 노드를 확정 처리

            for y, w in g[x]:                                            # 현재 노드 x의 모든 이웃 y와 간선 비용 w를 순회
                new_dist = cur_dist + w                                  # x를 거쳐 y로 가는 새로운 거리 후보를 계산
                if new_dist < dist[y]:                                   # 더 짧은 경로를 찾았다면
                    dist[y] = new_dist                                   # 최단거리 배열을 갱신
                    heapq.heappush(heap, (new_dist, y))                  # 갱신된 거리로 힙에 삽입하여 후속 탐색

        return -1                                                        # 목적지에 도달하지 못하면 -1 반환

3. 마무리

계속해서 문제는 풀고 있었지만 글을 올리지 않았었다.
다시 꾸준히 글을 올리자.