일정 재구성

• 리트코드 332번 문제 : https://leetcode.com/problems/reconstruct-itinerary/
• [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라.
• 단, 여러 일정이 있는 경우 사전 어휘순으로 방문한다.

• 입력 : tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
• 출력 : ["JFK", "MUC", "LHR", "SFO", "SJC"]

풀이 1) DFS 사용

• 시행 착오 :
  • 출발지 기준으로 도착지를 사전식으로 정리하여 딕셔너리를 만듭니다.
  • 그런 후, JFK 출발지로 하여 도착지를 방문하고, 해당 도착지 삭제한 후 계속 DFS를 하려고 했으나, 첫 도착지가 마지막 도착지인지, 아닌지 판단하기가 어려워서 기준을 잡지 못하였다.

• 실행 속도 : 80 ms
• 첫 도착지가 마지막 도착지일 가능성을 배제할 수 없으므로, 방문하면서 경로를 추가하는 것이 아니라 DFS로 다 방문한 후 역순으로 정리되면서 경로를 추가하는 방법을 사용한다.
• 이렇게 될 경우, 전체 경로는 역순이되며 다시 역전을 시켜서 반환하여 주어야한다.

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        cities = collections.defaultdict(list)
        result = []
        for from_city, to_city in sorted(tickets, reverse=True):
            cities[from_city].append(to_city)

        def dfs(from_city):

            while cities[from_city]:
                dfs(cities[from_city].pop())
            result.append(from_city)

        dfs("JFK")
        return result[::-1]