ch13-2(leetcode 787). K 경유지 내 가장 저렴한 항공권

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 787번 ( https://leetcode.com/problems/cheapest-flights-within-k-stops/ )

 

DFS를 사용한 풀이(시도 but 실패)

class Solution(object):

    def findCheapestPrice(self, n, flights, src, dst, k):
        visited = set()
        graph = collections.defaultdict(list)
        for a, b, c in flights:
            graph[a].append([b, c])

        totalPrice = [2**31 -1]

        def dfs(node, price, times):
            if node in visited:
                return
            if node == dst:
                totalPrice[0] = min(totalPrice[0], price)
            if times > k:
                return
            else:
                times += 1
                while graph[node]:
                    entry = graph[node].pop(0)
                    dfs(entry[0], entry[1]+price, times)
                times -= 1
                visited.add(node)

        dfs(src, 0, 0)
        if (totalPrice is None) or totalPrice[0] == 2**31-1:
            return -1
        return totalPrice[0]

 

✅접근 방법

스택으로 DFS를 구현하고 다익스트라 알고리즘을 사용해서 풀 수 있다. 

 

다익스트라의 경우 이전 문제처럼 최소 힙을 구현한 heapq 모듈을 사용해서 풀 수 있다. 

다익스트라 알고리즘은 단순히 노드를 순회하면서 거리(dist) 값을 더 적은 것으로 업데이트하는 것이 아니라서 헷갈릴 수 있다. 탐색할 다음 노드를 정할 때 임의로 정하지 않고, 현재 노드에서 가장 거리가 적은 노드로 업데이트를 해야 한다. 

직접 구현하는 방법도 있지만 대부분 가장 거리가 적은 다음 노드를 불러올 때 최소 힙 등이 구현된 모듈을 사용하면 시간을 절약할 수 있다. 

 

✅구체적인 순서

1. 탐색 중인 노드에 대해서 출발점부터 현재 노드까지의 거리(price)와 탐색한 횟수(k) 정보를 저장하고 있는 변수를 만든다. 이때 key는 현재 노드, value는 리스트 형식으로 [현재 노드와 인접한 노드, 그 노드까지의 거리]를 나타낸다.  

graph = collections.defaultdict(list)
    for a, b, c in flights:
        graph[a].append([b, c])

 

2. heapq 모듈을 적용하기 위한 튜플-리스트 변수(여기서는 Q)를 선언한다. 이때 리스트 내부의 튜플은 (거리, 현재 노드, 탐색 횟수)를 정보로 갖고 있다. 거리를 제일 앞에 두는 이유는 heapq 모듈에 원소를 넣고 정렬할 때 튜플의 가장 앞 순서를 가장 우선으로 정렬하기 때문이다. 

times = 0
Q = [(0, src, times)]

 

그리고 스택으로 DFS 탐색을 할 경우 while문을 사용하며 스택 변수에 원소가 없어질 때까지 특정 로직을 반복한다. 

while Q:
    // 내부 로직

 

while문 내부 로직

3. min heap의 특성상 힙 내부에서 가장 거리가 작은 값만 리턴한다. 따라서 이 값들 중 dst(도착점)과 같은 노드가 있다면 탐색을 종료해도 무방하다. -> 해당 로직 만들기

price, node, times = heapq.heappop(Q)
if node == dst:
    return price

 

4. 또한 최소 힙에서 나온 탐색 횟수의 값이 제한된 탐색 횟수(k)보다 많다면 해당 노드에 대해선 DFS 탐색을 더 이상 실행하지 않는다. 

5. 위 조건을 만족할 경우 해당 노드의 주변 노드에 대해 탐색을 실행한다. 해당 노드의 주변 노드가 무엇인지 알기 위해서는 1번에서 선언한 변수를 사용한다. 

if times <= k:    
    times += 1
    for b, c in graph[node]:
        alternative = price + c
        heapq.heappush(Q, (alternative, b, times))

 

6. while문이 끝나도 도착점을 찾지 못했으면 -1을 리턴한다. 

 

✅불필요한 탐색 방지 로직

(다른 블로그를 참고했습니다.)

그런데 이대로 구현하면 input 개수가 많은 테스트케이스에 의해서 타임아웃이 뜬다. 로직은 맞지만 불필요한 탐색이 실행되고 있기 때문이다. (여러 노드가 얽힌 경우 순환 구조가 만들어지면서 이미 탐색한 노드를 또 탐색하게 된다.) 따라서 추가적인 로직이 필요하다. 

이미 탐색을 진행했고 노드의 값(price)이 최소 힙에서 나온 값보다 작다면, 이미 최소값에 대해서 탐색이 끝난 노드이므로 추가로 탐색할 필요가 없다. 구현하기 위해서는 어떤 노드를 탐색했고, 해당 노드의 값이 얼마인지를 저장하는 변수가 필요하므로 빈 딕셔너리 변수를 선언하자. 

visited = {}

if node not in visited or visited[node] < times:
    visited[node] = times

 

 

참고한 포스트

https://8iggy.tistory.com/115