[파이썬 알고리즘 인터뷰] 38. 일정 재구성

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

38. 일정 재구성

leetcode 332. Reconstruct Itinerary 문제입니다.

leetcode.com/problems/reconstruct-itinerary/

 

 

풀이

 여행 일정을 그래프로 구성해서 dfs로 푸는 풀이입니다.

 

# 반복 dfs 풀이
def itinerary(self, ticket):
    graph = collections.defaultdict(list)
    for a, b in sorted(ticket):
        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]
    
# 재귀 dfs 풀이
def itinerary(self, ticket):
    graph = collections.defaultdict(list)
    for a, b in sorted(ticket):
        graph[a].append(b)

    route = []

    def dfs(a):
        while graph[a]:
            dfs(graph[a].pop(0))
        route.append(a)

    dfs('JFK')
    return route[::-1]