[알고리즘][그래프] - 7. 일정 재구성

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/reconstruct-itinerary/

[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘순으로 방문한다.

---

[DFS로 일정 그래프 구성]

import collections


class Solution(object):
    def findItinerary(self, tickets):
        graph = collections.defaultdict(list)
        for a, b in sorted(tickets):
            graph[a].append(b)

        route = []

        def DFS(a):
            while graph[a]:
                # 첫 번째 값을 읽어서 어휘순으로 방문한다.
                DFS(graph[a].pop(0))
            route.append(a)

        DFS("JFK")

        return route[::-1]

[스택 연산으로 큐 연산 최적화 시도]

import collections


class Solution(object):
    def findItinerary(self, tickets):
        graph = collections.defaultdict(list)
        for a,b in sorted(tickets, reverse=True):
            graph[a].append(b)

        route = []

        def DFS(a):
            while graph[a]:
                # 첫 번째 값을 읽어서 어휘순으로 방문한다.
                DFS(graph[a].pop())
            route.append(a)

        DFS("JFK")

        return route[::-1]

[일정 그래프 반복]

import collections


class Solution(object):
    def findItinerary(self, tickets):
        graph = collections.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]