[LeetCode] Reconstruct Itinerary

첫 번째 제출

from collections import defaultdict
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        t_dic = defaultdict(list)
        for s, e in sorted(tickets):
            t_dic[s].append(e)
    
        def dfs(s):
            while t_dic[s]:
                dfs(t_dic[s].pop(0))
            result.append(s)

        result = []
        dfs('JFK')
        return result[::-1]

조건 : 모든 티켓을 다 사용해야 함. = 가장 깊이 들어가야 함.

가장 깊이 들어간 첫번째 거를 가져오면 되기 때문에 t_dic이랑 result 전역변수를 그냥 바꿔도 됨.
t_dic 값이 pop 때문에 제거되면서 while문 돌때마다 하나씩 지워지고 하나씩 dfs에 들어감.
모든 곳 다 방문해서 더이상 갈 곳이 없어지면 뒤에서부터 하나씩 dfs가 종료되어 result에 추가
뒤에서부터 추가된거니까 뒤집어서 return