332. Reconstruct Itinerary

문제

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

• If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
• All airports are represented by three capital letters (IATA code).
• You may assume all tickets form at least one valid itinerary.
• One must use all the tickets once and only once.

예시

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

풀이

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = {}
        for src, des in tickets:
            if not graph.get(src, None):
                graph[src] = [des]
            else:
                graph[src].append(des)
                
        [graph[k].sort() for k in graph.keys()]
        visited = []
        def dfs(src):
            while graph.get(src, None):
                des = graph[src].pop(0)
                dfs(des)
            visited.append(src)
        
        dfs('JFK')
        return visited[::-1]

이번 문제는 여행 출발지와 도착지로 이루어진 여러 개의 여행 일정을 하나의 연결된 일정으로 만들어주는 문제이다. 다행이도 주어지는 input 여행 일정에는 모든 도착지와 출발지가 이어져 하나의 일정으로 만들어 질 수 있다고 생각됐다.

그렇게 되면 이 문제도 첫 출발지부터 시작해 연결되는 노드를 끝까지 찾아가는 dfs 문제라고 여겨졌고 도착지에서 출발지로 변경되어 다음 도착지를 찾는 과정을 계속하는 재귀문을 사용하게 되었다.

여행 일정은 dictionary의 list 형태로 받게 되었고 출발지를 dictionary의 key로 도착지를 value로 설정하였다. 그래서 출발지를 조회하게 되어 value가 모두 사라질 때까지 탐색을 반복하는 것으로 하였다.