리트코드 332번 Reconstruct Itinerary (python)

Problem

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

Solution

from typing import List
from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        ticket_dict = defaultdict(list)
        for f, t in sorted(tickets, reverse=True):
            ticket_dict[f].append(t)
        result = []

        def dfs(city: str):
            while ticket_dict[city]:
                dfs(ticket_dict[city].pop())
            result.append(city)

        dfs("JFK")

        return result[::-1]

정렬된 defaultdict를 통해 어휘 순으로 방문할 수 있다.

Reference

파이썬 알고리즘 인터뷰 38번