❗️[LEET CODE] 332. Reconstruct Itinerary

# Problem

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"]. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.   Constraints: 1 <= tickets.length <= 300 tickets[i].length == 2 fromi.length == 3 toi.length == 3 fromi and toi consist of uppercase English letters. fromi != toi

 

# My Answer

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        result=["JFK"]
        def dfs(ticketlist):
            if len(ticketlist)==0:
                return
            temp=[]
            for ticket in ticketlist:
                if ticket[0]==result[-1]:
                    temp.append(ticket)
            if len(temp)>=2:
                temp = sorted(temp,key=lambda x:x[1])
            result.append(temp[0][1])
            ticketlist.remove(temp[0])
            temp=[]
            dfs(ticketlist)
        dfs(tickets)    
        return result

[["JFK","KUL"],["JFK","NRT"],["NRT","KUL"]] 처럼 답이 한가지인 경우가 있을 수 있음

이 땐 사전순이 아니라 JFK-NRT-KUL 순서로 와야한다

 

# Solution 1 - DFS로 일정 그래프 구성

import collections

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        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]

반복할 때 내부를 다 돌고 나와서 자기 자신을 추가하므로 어휘순 방문해야함 -> 마지막에 반대 순서로 뒤집기

[["JFK","KUL"],["JFK","NRT"],["NRT","KUL"]] 의 경우

KUL 은 이어지는 원소가 없으므로 자기자신만 결과리스트에 추가하고 다음 차례로 넘어간다.

 

# Solution 2 - 스택 연산으로 큐 연산 최적화 시도

import collections

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        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]

pop(0)은 시간복잡도가 O(n) --> stack pop() 이용 (시간복잡도 O(1) )

처음부터 그래프를 역순 구성

 

# Solution 3 - 일정 그래프 반복

import collections

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        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]

while문을 돌면서 stack[-1]이 계속 바뀐다