Published:
Updated:

  • Reference
  • graph
    • λ°±μ€€: List
    • LeetCode: defaultdict(list)


SolutionPermalink

import collections
from typing import List


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

        for x, y in sorted(tickets):
            graph[x].append(y)

        def dfs(x: str):
            # μž¬κ·€λ‘œ λ‹€ λ°©λ¬Έν•œλ‹€λŠ” 뜻
            while graph[x]:
                # μ–΄νœ˜ 순 λ°©λ¬Έ -> κ°€μž₯ 첫 번째 κ°’
                dfs(graph[x].pop(0))

            answer.append(x)

        dfs('JFK')

        answer.reverse()
        return answer

Leave a comment