332. Reconstruct Itinerary

JFK에서 출발해서 지나가는 경로들 다 빼주면서 끝에 도달하면 역순으로 저장해줌.
JFK->A->B면 B에서 끝에 도달한거니 [B, A, JFK]로 저장하니 이제 구한거를 다시 뒤집으면 정답임.

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        tickets.sort()

        for first, second in tickets:
            graph[first].append(second)


        def dfs(depart):
            while graph[depart]:
                dfs(graph[depart].pop(0))
            answer.append(depart)
            
        answer = []
        dfs('JFK')

        return answer[::-1]

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