greentea31's Note

https://leetcode.com/problems/reconstruct-itinerary

풀이 과정

JFK에서 시작하는, 주어진 모든 비행 티켓을 사용하는 여행 경로를 구하는 문제이다. 경로는 여러가지가 존재할 수 있지만 사전식 순서로 앞선 경로만을 출력해야 한다.

비행기 티켓을 딕셔너리에 전부 넣어놓고, JFK에서 시작해 DFS 방식으로 사전식 순서가 앞선 도착지를 우선으로 탐방하여 문제를 해결하였다.

소스 코드

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        answer = []
        for depart, arrive in sorted(tickets, reverse=True):
            graph[depart].append(arrive)
        
        def dfs(x):
            while graph[x]:
                dfs(graph[x].pop())
            answer.append(x)
        
        dfs('JFK')
        return answer[::-1]