LeetCode #1976 Number of Ways to Arrive at Destination

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #1976 Number of Ways to Arrive at Destination

문제 풀이

다익스트라로 풀어야 함은 알고 있었는데 마냥 각 노드까지의 경로 길이 체크하고 그 이하인 경우에만 진행하여 목적지에 도달했을 경우 1씩 더해 탐색이 종료될 때까지 반복하게 해봤다. 결과는 TLE 에러. 풀이를 보니 약간의 dp 개념을 섞어서 탐색을 끝까지 진행하지 않고 중간에 끊었어야 했다.

• 각 노드에 도달하는 경로를 기록할 카운팅 배열 정의(0으로 초기화)
• 각 노드의 최단 거리를 기록할 거리 배열 정의(INF로 초기화)
• 0번 노드의 경로 거리는 0이고 경로 개수는 1로 설정
• 큐에 (0,0) = 거리, 탐색점 삽입
• 큐에 원소가 존재하는 동안 우선순위 큐로 pop하여 비용, 탐색점 정의
  • 탐색점이 목적지이면 카운팅 배열의 요소 나머지 연산하여 리턴
  • 경유지라면 경유지와 연결된 노드들에 대해 비용 + 노드 간 거리가 거리 배열의 값과 같으면 탐색점에서 경유지까지 접근이 가능하므로 dist[탐색점] 값을 더한다. 만약 더 작다면 탐색점에서 경유지로 가는 경우가 유일하게 인정되므로 경유지의 경로 개수를 탐색점의 값으로 바꾼다.

python 코드

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        board = collections.defaultdict(list)
        for srt, dst, cost in roads:
            board[srt].append((dst, cost))
            board[dst].append((srt, cost))
        cnt = [0] * n
        dist = [float('inf')] * n
        cnt[0], dist[0] = 1, 0
        q = [(0, 0)]
        while q:
            cost, dest = heapq.heappop(q)
            if dest == n - 1:
                return dist[dest] % (10 ** 9 + 7)
            else:
                for v, c in board[dest]:
                    nc = cost + c
                    if nc == dist[v]:
                        cnt[v] += cnt[dest]
                    elif nc < dist[v]:
                        cnt[v] = cnt[dest]
                        dist[v] = nc
                        heapq.heappush(q, (nc, v))