LeetCode 332. Reconstruct Itinerary

파이썬 알고리즘 인터뷰 문제 38번(리트코드 332번) Reconstruct Itinerary
https://leetcode.com/problems/reconstruct-itinerary/

나의 시도1(미해결)

# Maximum recursion depth error 발생
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        result = []

        start_to_end = dict()

        for ticket in tickets:
            start, end = ticket
            if start not in start_to_end:
                start_to_end[start] = [end]
            else:
                start_to_end[start] += [end]
        
        for ticket in start_to_end:
            start_to_end[ticket].sort()
        
        def helper(path, start, fromt_to):
            if not fromt_to:
                result.append(path[:])
                return
            if start not in fromt_to:
                path.pop()
                if path[-1] not in fromt_to:
                    fromt_to[path[-1]] = [start]
                else:
                    fromt_to[path[-1]] += [start]
                
                helper(path, path[-1], fromt_to)
            else:
                for end in fromt_to[start]:
                    fromt_to[start].remove(end)
                    if not fromt_to[start]:
                        del fromt_to[start]
                    path.append(end)
                    helper(path, end, fromt_to)
                    path.pop()
                    if start not in fromt_to:
                        fromt_to[start] = [end]
                    else:
                        fromt_to[start] += [end]
        helper(["JFK"], "JFK", start_to_end)
        return min(result)

나의 시도2(미해결)

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 = []
        stack = ['JFK']

        while stack:
            start = stack.pop()
            route.append(start)
            stack += graph[start]
            graph[start] = []

        return route

다른 풀이1(recursion)

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 helper(start):
            while graph[start]:
                helper(graph[start].pop())
            route.append(start)
        
        helper('JFK')
        return route[::-1]

다른 풀이2(Iteration)

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 = []
        stack = ['JFK']

        while stack:
            while graph[stack[-1]]:
                stack.append(graph[stack[-1]].pop())
            route.append(stack.pop())

        return route[::-1]

오답 및 배울 점1

def backtrack(path, start):
    if 조건 만족:  
        정답 경로 저장
        return
    for 후보 in 가능한 경로:
        path.append(후보)  # 경로 추가
        backtrack(path, 후보)  # 재귀 탐색
        path.pop()  # 되돌리기 (백트래킹)

• 위와 같은 백트래킹을 거의 고정된 공식처럼 쓰고 있었다.
• 지금 문제에서, 특정 도시에서 다음으로 갈 도시를 고를 때, 사전식으로 가장 빠른 도시를 골라 가게 되면 경로가 더 이상 이어지지 않는 경우가 있다.
• 이런 경우 위의 방법처럼 path.append(), path.pop() 하며 탐색해야 된다고 생각했다.
• 그런데 풀이를 보니 그냥 모든 경우를 dfs탐색하였다.
• 처음에는 백트래킹을 하지 않는 것이 이해가 되지 않았다.
• 어떻게 되는 것인가 하고 손으로 그려보니 tree가 그려진다. 그리고 저장되는 것이 바로 후위 탐색(Postorder Traversal)이었다. tree 가 주어졌을 때 후위 탐색을 한다고 하면, 모든 노드를 탐색하는 것이므로 백트래킹을 하는 것이 아니다.
• 그리고 그래프를 그려 풀이를 보니 직관적으로 이해가 되었다. 일단 이웃한 도시 중 사전식으로 가장 빠른 도시를 택하면서 길이 막힐 때까지 진행하고, 길이 막히면 그 경로를 되돌아오며 저장한다. 다른 경로가 있을 때까지 돌아온 후, 다음으로 빠른 도시를 방문한다. 이제 tree의 후위 탐색 을 알고 있다면, 완벽히 같은 과정임을 직관적으로 알 수 있다.

오답 및 배울점2

• 재귀(recursive)말고 반복(iteration)풀이도 시도해보았다. stack을 사용하여 접근하였으나 중간에 경로가 끊어지는 부분을 처리하지 못했다.
• 여러모로 복습이 필요하다.