[LeetCode/Python] 332. 일정 재구성(Reconstruct Itinerary)

[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라.

여러 일정이 있는 경우 사전 어휘 순(Lexical Order)으로 방문한다.

 

example:

 

Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]

 

Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

 

 

 

** 깔끔한 풀이 **

 

1. DFS로 일정 그래프 구성

 

 

class Solution:
    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]

 

풀이:

 

우선 tickets를 그래프에 정리해야 한다.

 

defaultdict를 이용하여 graph[a]에 아무것도 없어도 새로 생성해서 b를 추가할 수 있도록 한다.

 

line 5에서 sorted를 하지 않으면 graph에 정렬이 되지 않고 값이 들어가기 때문에 그리 했다.

 

이후 pop(0)을 이용하여 거쳐간 경로는 지워버렸다.

 

이 경우 역순으로 입력되기 때문에 리턴할 때 route를 뒤집어 주었다.

 

 

 

 

 

2. 스택 연산으로 큐 연산 최적화 시도

 

 

class Solution:
    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]

 

해설:

 

1번 코드에서는 pop(0)을 사용하였기 때문에 시간 복잡도가 O(n)이었지만

 

pop()을 할 경우 O(1)이 되기 때문에 이왕이면 pop()을 쓰는 것이 바람직하다.

 

따라서 애초에 pop()을 사용할 수 있도록 graph에 넣어줄 때 거꾸로 넣어주면 된다.

 

 

 

3. 일정 그래프 반복

 

 

class Solution:
    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]

 

해설:

 

재귀가 아닌 스택으로 풀이하였다.

 

경로가 끊어지는 케이스를 고려하여

 

stack이라는 변수를 만들었다.

 

진행하다가 graph[stack[-1]]이 비는 경우가 생기면

 

( = 경로가 끊어짐)

 

stack.pop()을 통해 route에 넣고 다시 스택 구성을 진행한다.