[leetcode]1976. Number of Ways to Arrive at Destination

리트코드 1976번 문제는 그래프의 최단경로를 찾는 문제입니다.

https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/

“알고리즘 트레이닝”에서 그래프에서 최단 경로 구하는 방법을 3가지 소개하고 있는데요.

( 벨만-포드 알고리즘 / 다익스트라 알고리즘 / 플로이드-워셜 알고리즘 )

이번 문제에서는 다익스트라 알고리즘을 사용해서 문제를 풀어봅니다.

다익스트라 알고리즘은 음수 간선이 없을때 사용할 수 있는 알고리즘으로 우선순위 큐 를 사용합니다.

그래프 문제는 먼저 input을 어떤 데이터로 표현할지부터 선택합니다.

저는 인접리스트로 표현해서 데이터를 사용합니다.

1976번 문제는 방향성이 없기 때문에 양방향으로 인접 리스트를 표시해줘야합니다.

adj = [[] for _ in range(n)]
        
for (s,d,w) in roads:
    adj[s].append((d,w)) #무방향성
    adj[d].append((s,w)) #무방향성

adj = [[] for _ in range(n)]

for (s,d,w) in roads:

adj[s].append((d,w)) #무방향성

adj[d].append((s,w)) #무방향성

그리고 다익스트라 알고리즘을 사용하여 그래프의 최단 경로를 구합니다

우선순위 큐를 사용하여 현재 노드의 최단 경로와 이전 노드의 최단 경로 + 인접 리스트에서 확인가능한 간선의 가중치를 확인하여 최소값으로 update 합니다.

distance = [float('inf')] * n
while q :
    a = list(heappop(q))[1]

    if visited[a] :
        continue
    visited[a] = True
             
    for (d,w) in adj[a]:
        if distance[a] + w < distance[d]: #최단 거리 비교
            distance[d] = distance[a] + w
            heappush(q, (distance[d] , d)) #최단거리에서 추가 탐색

distance = [float('inf')] * n

while q :

a = list(heappop(q))[1]

if visited[a] :

continue

visited[a] = True

for (d,w) in adj[a]:

if distance[a] + w < distance[d]: #최단 거리 비교

distance[d] = distance[a] + w

heappush(q, (distance[d] , d)) #최단거리에서 추가 탐색

다익스트라는 최초 거리를 inf 로 초기화 한 후 각 노드까지의 거리를 저장하고 탐색 과정에서 값을 줄여나가는 알고리즘이다.

알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)

1976번 문제의 경우 최단 경로 혹은 최단 거리를 찾는 문제가 아니라 최단 경로로 도착할 수 있는 경우의 수를 찾는 문제기 때문에 조금 trick이 필요하다.

다익스트라 알고리즘이 각 노드를 탐색할때 최소한의 거리 기준으로 탐색해서 나간다면 노드 n 으로 갈 수 있는 경우의 수는 노드 n 에 동일한 거리값으로 도착 할 수 있는 n-1 노드의 경우의 수 합이다.

if weight[w] == weight[n-1] + w:

dp[n] += dp[n-1]

for (d,w) in adj[a]:
    if distance[a] + w < distance[d]:
        distance[d] = distance[a] + w
        heappush(q, (distance[d] , d))
        dp[d] = dp[a] 

    elif distance[a] + w == distance[d]:   
        dp[d] += dp[a] #d에 도착하는 경우의 수는 a 의 경우의 수들의 합

for (d,w) in adj[a]:

if distance[a] + w < distance[d]:

distance[d] = distance[a] + w

heappush(q, (distance[d] , d))

dp[d] = dp[a]

elif distance[a] + w == distance[d]:

dp[d] += dp[a] #d에 도착하는 경우의 수는 a 의 경우의 수들의 합

다익스트라 알고리즘으로 최소 거리를 구하는건 우선순위 큐로 금방 할 수 있었지만, 경우의 수를 찾기 위해서는 많은 고민이 필요했던 문제.

1976번 문제를 풀었던 순서입니다.

입력값을 인접 리스트로 표현
다익스트라 알고리즘으로 최단 거리 구하기
최단 거리 구하는 과정에서 경우의 수 찾기

https://github.com/sok891111/leetcode/blob/main/WEEK26/1976.%20Number%20of%20Ways%20to%20Arrive%20at%20Destination.py