📌 40) 네트워크 딜레이 타임 ( 리트코드 743. Network Delay Time )
✔ 풀이 (다익스트라 알고리즘 구현)
from collections import defaultdict
import heapq
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
#그래프 구현
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w)) #(정점, 걸린시간)
#bfs
visited = {} #방문한 노드
Q = [(0, k)] #우선순위 큐 (시간, 정점)
while Q:
time, node = heapq.heappop(Q)
if node not in visited:
visited[node] = time
for v, w in graph[node]:
heapq.heappush(Q, (time + w, v)) #(시간, 정점)추가
if len(visited) == n: #모든 노드 신호 받음
return max(list(visited.values()))
return -1 #모든 노드 신호 받지 못함📌 41) K경유지 내 가장 저렴한 항공권 ( 리트코드 787. Cheapest Flights Within K Stops )
실패한 풀이 (시간제한 초과)
from collections import defaultdict
import heapq
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w)) #(도착 정점, 비용)
Q = [(0, src, k + 1)] #(비용, 출발 정점, 지나온 노드 개수)
while Q:
price, node, cnt = heapq.heappop(Q)
#도착지에 도착했을 경우
if node == dst:
return price
if cnt:
for v, w in graph[node]:
heapq.heappush(Q,(price + w, v, cnt - 1))
return -1input 👇
n = 13
flights = [[11,12,74],[1,8,91],[4,6,13],[7,6,39],[5,12,8],[0,12,54],[8,4,32],[0,11,4],[4,0,91],[11,7,64],[6,3,88],[8,5,80],[11,10,91],[10,0,60],[8,7,92],[12,6,78],[6,2,8],[4,3,54],[3,11,76],[3,12,23],[11,6,79],[6,12,36],[2,11,100],[2,5,49],[7,0,17],[5,8,95],[3,9,98],[8,10,61],[2,12,38],[5,7,58],[9,4,37],[8,6,79],[9,0,1],[2,3,12],[7,10,7],[12,10,52],[7,2,68],[12,2,100],[6,9,53],[7,4,90],[0,5,43],[11,2,52],[11,8,50],[12,4,38],[7,9,94],[2,7,38],[3,7,88],[9,12,20],[12,0,26],[10,5,38],[12,8,50],[0,2,77],[11,0,13],[9,10,76],[2,6,67],[5,6,34],[9,7,62],[5,3,67]]
src = 10
dst = 1
k = 10
다음과 같은 테스트케이스에서 Time Limit Exceeded 발생
해당 문제를 해결하기 위해 이미 방문한 노드는 방문하지 않도록 visited = {}을 사용 👇
from collections import defaultdict
import heapq
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w)) #(도착 정점, 비용)
visited = {} #방문 한 노드 기록 -> {노드 : 비용}
Q = [(0, src, k + 1)] #(비용, 출발 정점, 지나온 노드 개수)
while Q:
price, node, cnt = heapq.heappop(Q)
#도착지에 도착했을 경우
if node == dst:
return price
if cnt and node not in visited:
visited[node] = price
for v, w in graph[node]:
heapq.heappush(Q,(price + w, v, cnt - 1))
return -1input 👇
n = 5
flights = [[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]]
src = 0
dst = 2
k = 2
다음과 같은 테스트케이스에서 통과하지 못함
👉 방문한 노드를 무조건 방문하지 않도록 하는 로직을 방문한 노드일 경우, 경유지의 개수가 더 작으면 값을 변경하여 추가 하는 로직으로 변경
👇👇👇👇👇👇👇👇👇
✔ 최종 풀이 (다익스트라 알고리즘 응용)
from collections import defaultdict
import heapq
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w)) #(도착 정점, 비용)
visited = {} #방문 한 노드 기록 -> {노드 : 남아있는 경유지의 개수}
Q = [(0, src, k + 1)] #(비용, 출발 정점, 남아있는 경유지의 개수)
while Q:
price, node, cnt = heapq.heappop(Q)
#도착지에 도착했을 경우
if node == dst:
return price
if cnt and (node not in visited or visited[node] < cnt):
#방문하지 않은 노드면 값 추가 /
#방문했던 노드지만 남아있는 경유지의 개수가 더 많으면 새로 값을 변경
visited[node] = cnt
for v, w in graph[node]:
heapq.heappush(Q,(price + w, v, cnt - 1))
return -1