ch12-7(leetcode 332). 일정 재구성

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 332번 ( https://leetcode.com/problems/reconstruct-itinerary/ )

 

시도한 방법

풀이에는 실패하였지만 시도한 방법은 기록해 두었다. 전체 코드는 다음과 같다. 

class Solution(object):

    def findItinerary(self, tickets):

        def dfs(elem, path):
            if len(path) >= (len(tickets)+1):
                result.append(path[:])
                return
            
            for e in route[elem]:
                route[elem].remove(e)
                dfs(e, path + [e])
                route[elem].insert(0, e)

        result = []
        min_result = None
        route = collections.defaultdict(list)
        for t in tickets:
            route[t[0]].append(t[1])
        
        for k in route.keys():
            dfs(k, [k])

        min_result = min(result, key=lambda x: "".join(x))
        return min_result

 

풀이 1. (교재 참고)

시도한 방법처럼 그래프에서 DFS를 통해 재귀적으로 탐색한다. 다만 앞서 시도한 방법에서는 마지막에 min() 함수로 알파벳 순 정렬을 하려고 했지만, 교재에서는 아예 주어지는 tickets 리스트를 알파벳 순서대로 정렬한 뒤에 탐색하고 있다. 

전자의 경우 탐색 가능한 여러 개의 방법이 전부 result라는 변수에 담기는 반면, 후자의 경우는 알파벳 순서상 제일 빠른 방법만 담기게 되어서 후에 추가로 정렬을 안 해도 된다. 

 

여기서도 딕셔너리 변수 graph를 만들어서 key값 노드에서 이동할 수 있는 노드들을 리스트 형태로 value에 추가한다. 

예를 들어서 tickets 변수에 ["AAA", "BBB"], ["AAA", "CCC"] 가 포함되어 있다면,

graph["AAA"] = ["BBB", "CCC"] 가 된다. 

for key, value in sorted(tickets):
    graph[key].append(value)

 

graph 딕셔너리에 key값이 있는지 없는지 확인하지 않고 바로 value 값을 추가할 수 있는 이유는 graph 변수를 dict()이 아니라 collections.defaultdict()으로 선언하였기 때문이다. 

collections.defaultdict()의 경우 찾는 key가 없어도 오류를 리턴하지 않는다. 반면 dict()은 없는 key를 조회하면 오류가 발생한다. 

 

이제 dfs()를 호출해서 탐색을 시작한다.

하나의 티켓을 사용할 경우 graph 변수에서 해당 (key, value) 쌍을 제거해서 다음번에는 사용할 수 없도록 한다. 

앞서 graph의 각 key에 해당하는 value인 리스트의 각 원소들을 알파벳 순으로 정렬하였기 때문에, 탐색할 때도 앞에서부터 탐색해 주어야 한다.

 

리스트는 투 포인터가 아니기 때문에 pop(제거하려는 index) 으로 특정 인덱스의 값을 제거할 수 있다. 맨 앞의 원소를 제거하려면 pop(0)을 사용하고, 이 때의 시간복잡도는 O(n)이다. 리스트를 순회하면서 특정 인덱스를 찾아야 하기 때문이다. 

 

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

 

탐색할 경로가 더 이상 없을 경우 현재 위치의 노드부터 결과 변수인 route에 추가한다. 

그러면 경로의 맨 끝 지점부터 추가되기 때문에, 값을 리턴할 때에는 route 리스트의 역순으로 리턴하여야 한다. 

문자열 슬라이싱을 사용하면 간단하게 입력할 수 있다. 

return route[::-1]

 

풀이 2. (교재 참고)

두 번째 풀이는 첫 번째 풀이와 거의 같은데, 첫 번째 풀이 속도를 높이는 방법이다. 

앞서 알파벳 순으로 tickets를 정렬한 뒤 pop(0)을 사용하면서 O(n)이 소요되었다. 리스트가 작은 경우 속도에 큰 영향이 없지만 크기가 정말 클 경우에는 이런 연산에 따라서도 속도가 느려질 수 있다. 

 

리스트에서 pop(0)이 아니라 pop()을 사용하려면 알파벳을 역순으로 정렬한다. 

for key, value in sorted(tickets, reverse=True):
    graph[key].append(value)

 

풀이 3. (교재 참고)

재귀를 사용하지 않는 방법도 있다. 

재귀 문제를 사용하지 않고 while 문으로 처리하는 경우 스택을 많이 사용한다. 

 

앞의 방법처럼 route 변수는 결과를 저장하는 데 사용하고, stack 변수를 새로 선언해서 지금까지 탐색한 경로를 저장해두는 장소로 사용한다. 

처음 시작점은 "JFK"이므로 스택에 JFK를 먼저 넣는다. 

 

그 외의 tickets 리스트를 알파벳 순으로 정렬해서 사용하거나, 딕셔너리 graph 변수로 경로 정보를 저장한다거나, 경로를 탐색할 때마다 graph[key]에서 값을 하나씩 제거하는 것은 위의 방법과 똑같다. 

 

우선 스택에 원소가 있는지 확인한다. 

스택에 원소가 있다면, graph에서 해당 원소를 key값으로 조회했을 때 남은 value가 있는지를 확인한다. = 탐색할 경로가 있는지를 확인한다. 

둘 다 해당한다면, 스택 맨 위의 원소의 value값들 중 가장 앞에 있는(알파벳순이 제일 빠른) 값을 graph에서 제거하고, 그 값을 stack에 추가한다. 

 

리트코드에서 제시하는 1번 예시를 간단하게 보자. 

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

 

시작점이 "JFK"이므로 이 값에 대해서만 계산해 보자. "JFK" 의 value 값을 알파벳순으로 정렬해서 넣는다면,

graph["JFK"] = ["ATL", "SFO"]

 

초기 상태의 stack 변수에는 JFK만 있으므로 JFK가 스택의 맨 위의 원소다. 

해당 원소를 graph key로 했을 때 해당하는 값들 중 알파벳순으로 빠른 값을 불러오면 "ATL"이다. 

graph["JFK"] 의 값 리스트에서는 이 "ATL"을 제거하고, 이 값을 stack 변수에는 추가한다. 

그러면 stack = ["JFK", "ATL"] 이 된다. 

 

이처럼 스택 변수는 탐색하는 노드들을 모두 저장한다. 

이후 이 경로를 route 변수로 옮기는데, 스택의 특성상 pop()으로 값을 옮기면 route에는 역순으로 옮겨지게 된다. 

그러므로 역순 슬라이싱[::-1]을 사용해서 순서를 뒤집어서 리턴해 준다.