🎯 leetcode - 787. Cheapest Flights Within K Stops
🤔 나의 풀이
📌 문제
- 파이썬 알고리즘 인터뷰 41번 문제
- 다익스트라 알고리즘📌 날짜
2020.02.13📌 시도 횟수
2 try💡 Code
from collections import defaultdict
import heapq
class Solution:
def findCheapestPrice(self, n, flights: List[List[int]], src, dst, k) -> int:
graph = defaultdict(list)
for n1, n2, w in flights:
graph[n1].append((n2, w))
Q = [(0, src, 1)] # 가격, 정점, 경유지 수
while Q:
price, node, cnt = heapq.heappop(Q)
if cnt <= k + 2: # cnt가 범위 밖에 있는 정점이면 버린다.
if node == dst: # cnt가 범위 안이면서 정점이 도착점이면 리턴
return price
for n2, w in graph[node]: # 정점과 인접한 정점들을 Q에 담는다.
alt = price + w # 정점의 price에 자신의 가중치를 누적해서 더함
heapq.heappush(Q, (alt, n2, cnt + 1)) # cnt(경유지 수를 1개 추가)
return -1💡 문제 해결 방법
😸이전 문제(40번)의 다익스트라 알고리즘 코드를 일부 변형했다.
1. 그래프 인접 리스트를 defaultdict로 생성했다.
key는 시작 노드 / value는 (도착 노드, 가중치 값)으로 구성했다.
2. Q = [(가격, 정점, 경유지 수)] 를 생성했다. Q는 heapq로 처리될 것이다.
3. Q에 대하여 heapq.heappop(Q)를 하면 price가 최소인 노드의 가격(price),
정점(node), 경유지 수(cnt)를 얻을 수 있다.
4. 경유지 수(cnt)가 k+2(시작 정점, 도착 정점도 경유지 수에 포함)보다 작다면
정점이 도착점인지 판별한다.
5-1. 도착점이라면 현재 정점의 price를 리턴한다.
5-2. 아니라면 정점과 인접한 정점들을 다시 Q에 heappush 한다.
단, 새롭게 추가하는 정점들의 price는 이전 정점의 price에 graph[node]의
2번째 value 값인 w를 추가한 값이 되도록 한다. (price값은 누적된다)
6. 더이상 방문할 인접한 정점이 없을 때까지 3~6을 반복한다.
모든 정점을 방문했음에도 5-1에서 리턴되지 않았다면, -1을 리턴해서 프로그램을 종료한다.
💡 새롭게 알게 된 점
-❌ (한번에 맞추지 못한 경우) 오답의 원인
-😉 다른 풀이
📌 하나. k를 빼는 방법
import collections
import heapq
from typing import List
class Solution:
def findCheapestPrice(self, n, flights: List[List[int]], src, dst, k) -> int:
graph = collections.defaultdict(list)
# 그래프 인접 리스트 구성
for u, v, w in flights:
graph[u].append((v, w))
# 큐 변수: [(가격, 정점, 남은 가능 경유지 수)]
Q = [(0, src, K)]
# 우선 순위 큐 최소값 기준으로 도착점까지 최소 비용 판별
while Q:
price, node, k = heapq.heappop(Q)
if node == dst:
return price
if k >= 0:
for v, w in graph[node]:
alt = price + w
heapq.heappush(Q, (alt, v, k - 1))
return -1💡 문제 해결 방법
- 내 방법이랑 아주 조금 다른 방법이다.
- 나의 방법에서는 k를 더하면서 처음/끝 종점도 k에 포함시켜서 풀었고,
위의 방법은 k를 빼면서 처음/끝 종점은 k에 포함시키지 않았다.💡 새롭게 알게 된 점
-
열심히💨 (알고리즘 블로그)