Python Algorithm Q38

November 24, 2022

Q38 Reconstruct Itinerary

Q

You are given a list of airline tickets where tickets[i] = [from_i, to_i] 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.

Sample Input

Example 1

Input: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
Output: [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]

Example 2

Input: tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
Output: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
Explanation: Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”] but it is larger in lexical order.

Constraints

1 <= tickets.length <= 300
tickets[i].length == 2
from_i.length == 3
to_i.length == 3
from_i and to_i consist of uppercase English letters.
from_i != to_i

1. My Own Try

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        ans = []

        def remove(list: List[List], element: List):
            tmplist = list[:]
            tmplist.remove(element)
            return tmplist
        
        def dfs(leftTicketList: List, path: List):
            if len(path) > len(tickets):
                ans.append(path)
                return
            
            #실제로 바로 pass하더라도, 모든 value들을 한 번씩 비교해보는건 시간을 많이 잡아먹는듯 하다
            for N in leftTicketList:
                if(path[-1] ==  N[0]):
                    dfs(remove(leftTicketList, N), path + [N[1]])


        dfs(tickets, ["A"])
        ans.sort()
        return ans[0]

# test set

a = Solution()

b1 = [["A", "B"], ["B", "E"], ["D", "E"], ["B", "D"], ["E", "B"]]
b2 = [["A", "B"], ["B", "F"], ["B", "C"], ["C", "B"]]
b3 = [["J", "S"], ["J", "A"], ["S", "A"], ["A", "J"], ["A", "S"]]

a.findItinerary(b1)

야심차게 시도한 첫 번째 풀이지만 개같이 실패… 이유는 time-out이었다. exmaple에 나와있는 input이나 나름대로 만들어서 해본 set에서는 잘 나왔었는데 역시 어마무시한 size의 test case가 들어가니까 실패했다. 나름대로 시간을 줄인 건데도 아웃이라서 이후 풀이부터는 답안을 조금 참고했다. 간단히 설명하면 DFS를 반복해서 모든 티켓을 이용하는 경로를 전부 ans에 append 해놓고, 그걸 다시 sort해서 첫 번째 원소를 리턴했다. 하지만 input이 매우 커지면서 “모든 경로를 전부 탐색”하는 방식이 문제였던 것 같다.

2. My Own Solution

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

        for a, b in sorted(tickets):
            graph[a].append(b)

        def dfs(startfrom: str, path):
            if ans:
                return
            
            if len(path) > len(tickets):
                ans.append(path)
                return

            tmp = 0
            for N in graph[startfrom]:
                graph[startfrom].remove(N)
                dfs(N, path+[N])
                graph[startfrom].insert(tmp, N)
                tmp += 1

        start = "JFK"
        dfs(start, [start])
        # print(ans)
        return ans[0]

진짜 하루종일 고생한 끝에 겨우겨우 구해냈다. 순수하게 거의 4시간정도 쓴 것 같다. 일단 1번 시도가 거의 첫번째 try였는데 답을 구하기까지 굉장히 많은 실패가 있었다. 중요한 것만 몇개 꼽아보겠다.

1. graph로 자료 변환
  일단 자료의 형태를 graph로 바꾸어서 무의미하게 반복되는 loop를 최대한 많이 줄였다. for문에서 모든 N에 대해 lastDest와 비교하는 방식은 사실 단순무식한 N^x 꼴이라 타임아웃될 법 했다. 그래서 출발지끼리 묶은 딕셔너리를 만들었다.
1. if ans: return 추가
  위 풀이대로 해도 타임아웃이 떴다. for에서 처럼 완전 무의미한 루프는 줄었지만 그럼에도 불구하고 모든 트리를 다 탐색한다는 문제점이 있으므로 첫 번째 ans를 받은 순간 더 재귀를 진행할 이유가 없어서 ans에 원소가 하나라도 들어오면 사실상 재귀가 끝나도록 했다. 원래는 가능한 모든 경우의 수를 ans에 싹다 append하고 첫번째 요소를 return했다. 어짜피 그래프 만들때 sorted로 순서대로 그룹화했으니까 가장 첫번째로 append되는 경로가 무조건 답이었기 때문이다.
1. insert 위치 수정
  2번까지 진행하면 time-out은 안뜨는데 웬 쌩뚱맞은 wrong-answer가 뜬다. 진짜 모르겠다 하고 체념하려다가 발견해버렸다. line 19, 21을 보면 재귀에 들어가기 전에 타이밍을 맞춰서 미리 graph에서 빼고, 다음 재귀를 한다음에 그 재귀가 실패였으면 다시 append한다. 그래 바로 여기서 문제였다는 것이다. 이 방법은 이전 문제들에서 정답지가 보여준 예쁜 풀이여서 꼭 써보려고 했는데 하필 “사전식 배열” 문제에서 이걸 시도한게 패착이었다. 원래 insert 대신 append 썼을 때는 애가 분명이 돌았던 루프를 또 돌아서 ㅋㅋ 문제였고 이걸 치우려고 대충 맨 앞에 짱박아두려고 insert(0, element)를 했더니 이거 때문에 배열 순서가 바뀌어서 또 문제가 됐나보다. 설마 싶어서 tmp 변수 뚝딱 만들어서 임시로 index 역할을 하도록 시키고, remove했다가 빠진 그 자리에 그대로 insert 했더니 마침내 풀렸다.

진짜 푸느라 힘들었다. 당연하지만 시간을 아주 많이 먹는다…

3. Given Solution #1

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]

매번 느끼는 거지만 알고리즘 잘 짜는 사람들은 정말 ‘신’이다. 보면 굉장히 깔끔하고 간결하다. 코드를 짜다보면 예를 들어 특정 순간에서 exit해야 한다던지, index를 가져와야 한다는지 파생적인 문제가 생길 때가 있다. 그냥 변수 때려박아서 처리하면 내가 짠 ㅋㅋ 코드가 되는거고 아예 다른 문제가 생기지 않게 아주 깔끔한 구조로 짜면 이런 풀이가 완성되는 것이다. 하나씩 풀어서 보자. 위에서 graph로 정리한 것까지는 동일하다. dfs를 정의할 때 넣은 인자 a는 출발 지점으로 볼 수 있다. 모든 graph[출발지점]에 대해서 dfs를 시도한다. 다음 재귀로 넘기는 그 순간, .pop(0)을 이용해서 해당 grpah tree의 첫 번째 원소를 graph로부터 “제거”하고, 동시에 그 첫번째 원소를 다음 재귀의 출발지점으로 넣는다. pop의 리턴값이 해당 element라는 것을 잘 이용해서 굉장히 아름답게 짰다.

처음 보고 ‘아 이렇게 했구나 신기하다’ 했다가, ‘어 이러면 순서가 꼬이는데?’ 했다가 실제로 순서가 꼬일 수 있는 경우에 대해 모두 시도해보아도 문제가 없는 것을 발견하고 다시 한 번 감탄했다. 말로 설명하기에는 힘들어서, 노트로 정리한 풀이를 첨부했다.

Free Memo-12

여기서 주목해야하는 점은 “결국 언젠가는 쓰이는 티켓”이라는 것이다. 위에 내 풀이에서 remove-insert를 보면 알겠지만 나는 해당 루트를 탐색하고, 그 탐색이 올바른 결과물이 아니라면 다시 “되돌리려고” 다시 insert했다. 그러니 그 하위 루트에 대해 컴퓨터가 열심히 연산해놔도, 처음부터 잘못된 길을 탔나면 나중에 다른 루트에서 또 새로 연산을 한다. 잘못된 루트의 “일부”였기 때문에 통째로 날렸기 때문.

하지만 이 풀이에서는 발상을 전환해서 시간 효율 측면에서도, 심미성 측면에서도 완벽한 답을 냈다. 바로 “언젠가는 끝이 나기 마련”이라는 것. 위에 첨부한 사진에서, 첫 번째 루트로 진입했을 때는 다른 티켓을 모두 다 사용하지 못하기 때문에 잘못된 루트이다. 그래서 나는 끝까지 가는 루트를 찾기 위해 현재 길이 > 총 티켓 수 라는 기준을 잡고 매번 검사시켰다. 하지만 다시 생각해보면, 어느 포인트에서건 “끝이 났다”라는 것은, 그 어떤 루트로 진입할지라도 거기서 끝이 난다는 것이다. 이 점을 고려하면, 처음으로 끝나는 곳에서부터 append를 시작해도 순서상 아무런 문제가 없다(역순은 문제가 되지 않는다). 내가 시작부터 잘못된 루트를 탔을지라도, 그 루트는 “언젠가” 무조건 쓰이게 된다, 아니, 조건에 의하면 쓰여야 한다.

다만 유일하게 주의해야 할 점은 그냥 pop()이 아니라 pop(0)을 써야한다는 점이다. 반복할 때 graph 원소의 앞에서부터 탐색해야 사전식 배열로 들어가기 때문.

4. Given Solution #2

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

        for a, b in sorted(tickets, reversed=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), pop()의 시간복잡도는 O(1)이다. 위에서 우리는 사전식 배열을 지키기 위해 맨 앞 element부터 pop시켰는데 만약 키별 리스트의 크기가 굉장히 컸다면 시간 소요가 훨씬 커졌을 것이다. 따라서 처음 graph를 만들 때 sorting을 처음부터 역순으로 시키면 pop()만 사용해도 문제가 생기지 않는다. leetcode의 test case에서는 큰 차이가 없지만 만약 훨씬 더 큰 tree가 주어져 키별 리스트의 크기(ex. a:[1~100])가 굉장히 커진다면 유의미한 차이가 발생했을 것이다.

5. Given Solution #3

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)) #stack이 아니라 graph에서 pop한다
            route.append(stack.pop())

        return route[::-1]

재귀 형식이 아니라 오랜만에 보는 stack 구조 풀이이다. 대부분의 재귀 문제는 반복으로 치환할 수 있다고 한다. 구조를 분석해보면 stack이 존재하는 한 계속 반복하는 구조이다. 함수(또는 원하는 특정 코드)를 반복시킬때 recursion을 이용해서 함수 자체로 구성된 stack을 쌓아갈 수도 있지만 말그대로 stack을 이용해서 반복할 수도 있다.

여기선 아예 끝이 날 때까지 stack에 append-pop을 반복하면서 다음 loop에는 더 길어진 stack을 넘겨주는 마치 재귀하듯이 반복된다. 그래프의 원소가 존재하는 한(다시 말하지만, for문이 아니라 존재하는 한이다) 계속 stack에 하위 계층의 첫 번째 branch를 쌓아 나간다. 거기서 끝을 마주치면 거기서부터 route에 차례로 append에 나가고 stack에서 빼내면서 다시 상위 계층으로 거슬러 올라간다. 올라가다 보면 분기점을 만나는데, 여기서 첫 번째 branch는 graph[].pop 됐으므로 더이상 존재하지 않는 경로이다. 따라서 이제 second branch로 탐색하게 된다. 반복하고, 또 반복해서 말하지만 “모든 티켓은 반드시 쓰인다”. 두 번째 루트를 타고 내려가다 보면 반드시!! 아까 first branch에서 지났던 ending을 다시 만나게 된다. 대충 느낌이 오는가? ending에서부터 조금씩 늘려가는 방식이다. 루트를 들리면 들릴 수록 점점 꼬리가 길어지다가 모든 티켓을 다 썼을 때 꼬리가 곧 온전한 전신이 된다.

내가 첫 번째 풀이에서 잘못된 설명을 했다는 것을 이제서야 알았다. “모든 경로를 탐색하는 방식이 문제”였다고 하는데, 가능한 모든 경로의 경우의 수를 탐색하는 것은 낭비가 맞지만, 티켓을 전부 사용하려면 당연하게 모든 경로를 탐색해야한다. 꼬리를 계속 늘려나가려면 모든 경로를 다 가봐야해서 그렇다. 대신 여기서 time-out이 나지 않는 이유는 이미 한 번 가봤던 꼬리는 다시 가지 않아도 되기 때문.

Overall Review

맨 처음에 문제를 봤을 땐 기존의 문제들과 비슷하게 풀리겠거니 싶었는데, 전혀 그렇지 않았다. 문제 자체에 걸려있는 lexical order 제약과 모든 티켓을 반드시 소모해야한다는 제약이 굉장히 큰 압박으로 다가왔기 때문. 단순하게 접근했을 때는 모든 경우의 수를 다 따져보다 보니 time-out을 굉장히 자주 겪었다. 그리고 이전처럼 tree 구조로 바꾸지 않고 그냥 풀어보려하다가 큰 코를 데여서 이제 이런 탐색 문제는 graph로 자료를 편집해야한다는 것도 배웠다. 정말 어려웠지만, 그만큼 많이 얻어간 문제.

Hyuntae H