문제 요약
시도&풀이 방법
코드
리뷰
문제 요약
정점, 간선, 경유 개수 제한, 출발 노드, 도착 노드에 대한 정보가 주어진다.
이때 경유 개수 제한에 만족하면서 출발 노드에서 도착 노드까지의 최단거리를 구하라
시도&풀이 방법
경유 제한이 없을 경우
경유 제한이 없을 경우 평범한 다익스트라 알고리즘 사용하여 구현해보고 그 다음 경유제한을 적용시켜 보기 위해 먼저 기본 다익스트라의 형태를 구현했다.
import heapq
from collections import defaultdict
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = defaultdict(dict)
min_heap = []
for u, v, w in flights:
graph[u][v] = w
if u == src:
heapq.heappush(min_heap, (w, v))
while min_heap:
cur_w, cur_src = heapq.heappop(min_heap)
if cur_src == dst:
return cur_w
for next_dst, w in graph[cur_src].items():
next_w = w + cur_w
if not next_dst in graph[src] or next_w < graph[src][next_dst]:
graph[src][next_dst] = next_w
heapq.heappush(min_heap, (next_w, next_dst))
return -1
경유 제한을 완전 무시하고 찾았기 때문에 당연히 정답이 아니다.
순차적으로 접근해보기 위해서 먼저 이렇게 구현해봤다.
경유 제한 조건 적용
경유 제한을 걸기 위해 다음과 같은 상황을 코드에 적용시켰다.
추가적으로 경유제한 때문에 한번 탐색한 정점을 다른 가중치로 재탐색이 진행 될 수 있기 때문에 그래프를 건드리지 않았다.
1. 힙에 넣을때 현재 진행상황에서 사용한 경유의 수 추가
2. 주어진 경유 제한 k 보다 현재 진행중인 탐색과정에서의 cur_k가 작다면 계속 탐색을 진행 할 수 있게 함, 반대로 같거나 작으면 더 이상 탐색을 못하게 continue
3. cur_k의 조건을 통과하고 진행중인 탐색에서 다음 정점을 방문하고자 할때 따로 조건을 걸지 않음, 경유의 제한 때문에 이동할 수 있는 모든 정점이 가중치에 상관없이 다음 탐색에서 바로 최단거리가 될 가능성이 존재하기 때문
class Solution:
def findCheapestPrice(self, n: int, flights, src: int, dst: int, k: int) -> int:
graph = defaultdict(dict)
min_heap = []
for u, v, w in flights:
graph[u][v] = w
if u == src:
heapq.heappush(min_heap, (w, v, 0))
while min_heap:
cur_w, cur_src, cur_k = heapq.heappop(min_heap)
if dst == cur_src:
return cur_w
if cur_k < k:
for next_dst, w in graph[cur_src].items():
next_w = w + cur_w
heapq.heappush(min_heap, (next_w, next_dst, cur_k + 1))
return -1이렇게 제출한 결과 통과할 줄 알았다.
그러나
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
위와 같은 입력값에서 시간초과 오류가 떴다.
cur_k의 조건 때문에 무한루프가 발생할 수는 없다.
그러나 경유 제한이 생각보다 널널하고 간선이 많으면서 사이클이 존재할 경우 시간복잡도가 너무 커져버리는 것 같다. pycham과 같은 IDE환경에서는 결과값이 나오기는 함 30초 정도 걸려서 -1출력
최소힙의 특성 이용
추가적인 조건이 필요하다.
이때 최소힙과 다익스트라의 특징을 이용해야 하는데 중요 특징은 이렇다.
최소힙에 의해서 뽑혀지는 정점, 가중치의 값들은 그 정점에 대해서 최단거리로 도착했다는 점이다.
가장 짧은 거리만을 선택하며 그 정점에 도착 했기 때문에 그 정점에 재방문을 하게 된다면 조건이 있어야지만 재방문을 허용할 수 있다.
여기서 그 조건은 처음 방문했을 당시의 경유의 수 보다 재방문시에 경유했던 수가 적어야 한다.
이미 처음 방문했을때의 경유의 수 보다 경유의 수가 더 큰데, 재방문을 허용한다면 어차피 목적지에 도달하지 못한다.
처음 방문했을때 조차 경유의 제한에 걸려 목적지에 도착을 못한 상황에서 재방문을 한다면 의미가 없는 방문이 된다.
이런 의미없는 방문을 줄이기 위해 재방문을 시도할때 경유의 수가 이미 방문했을때의 경유의 수 보다 적다면 재방문을 허용 시킬 수 있다.
경유의 수가 적기 때문에 재방문 후 목적지에 도착 할 수 있는 가능성이 있기 때문이다.
import heapq
from collections import defaultdict
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = defaultdict(dict)
min_heap = []
for u, v, w in flights:
graph[u][v] = w
if u == src:
heapq.heappush(min_heap, (w, v, 0))
visit = {}
while min_heap:
cur_w, cur_src, cur_k = heapq.heappop(min_heap)
visit[cur_src] = cur_k
if dst == cur_src:
return cur_w
if cur_k < k:
for next_dst, w in graph[cur_src].items():
next_w = w + cur_w
if not next_dst in visit or cur_k + 1 < visit[next_dst]:
heapq.heappush(min_heap, (next_w, next_dst, cur_k + 1))
return -1if not next_dst in visit or cur_k + 1 < visit[next_dst]:아예 처음 방문이거나 이미 방문했을때의 경유의 수보다 적어야 한다는 조건을 걸면 통과한다.
리뷰
처음에 경유의 제한을 걸었을때는 딱히 다른 조건들에 대해서 추가적으로 생각을 안했다.
그러나 재방문과 사이클관련해서 시간초과가 걸렸을때 왜 시간초과가 걸렸는지 생각하기까지 시간이 꽤 걸렸다.
다익스트라의 특징 즉 해당 정점에 대해서 최단거리만을 선택하며 도착했다는 사실과 경유제한이라는 조건과 연결시켜서 생각하기까지 쉽지 않았던 것 같다.
