Leetcode - 332. Reconstruct Itinerary

문제

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

풀이

처음에 그래프를 어떻게 구성해야 될지 전혀 감을 못 잡았다. 결국 풀지 못했다. 이 문제는 DFS와 순회 두 가지 방법으로 풀이가 가능하다.

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for a, b in sorted(tickets):
            graph[a].append(b)
            
        route = []
        def dfs(key):
            while graph[key]:
                dfs(graph[key].pop(0))
            route.append(key)
            
        dfs("JFK")
        
        return route[::-1]
        

DFS는 간단한데 순회 방법은 이해하기가 어려웠다.

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for a, b in sorted(tickets):
            graph[a].append(b)
            
        route, stack = [], ["JFK"]
        while stack:
            while graph[stack[-1]]:
                stack.append(graph[stack[-1]].pop(0))
            route.append(stack.pop())
        
        return route[::-1]
        

방문 경로는 stack 에 넣어놓고,  다 방문한 다음 route에는 순서대로 넣어준다고 생각하면 된다.