[파이썬 알고리즘 인터뷰][그래프] 일정 재구성

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

JFK에서 출발하는 여행 일정 구성

 

책에서 구현된 코드

    from collections import defaultdict
    
    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]

 

기억해야할 기법

• DFS를 제대로 활용하지 못함 -> 후위 탐색과 관련이 있는지?
  
  • 깊이를 탐색하면서(재귀하면서) 어떻게 결과를 형성해가야하는지 알아야함
  • 탐색할 때마다 city를 append하지 않고, 간선이 없을 때 push하며 형성해야함
  • 마지막에 city들을 reverse
• 아마 정답(경로)이 무조건 있다는 가정으로인해 가능한 듯
  • 탐색 중 간선을 하나씩 탐색하고 지우며, 간선이 없는 노드를 찾음
  • 이 노드가 경로의 마지막 city로써 append되는 것은 경로가 무조건 완성되기 때문
  • 경로가 무조건 완성되지 않으면, 이 city까지 경로가 도달하는지 보장이 되지 않음
• list of list의 sort
  • element인 list의 [0]로 sort하되, [0]가 같으면 [1]을 비교하여 자동으로 정렬함

 

내가 구현한 코드

# Fail
def findItinerary(tickets: list[list[str]]) -> list[str]:
    dic = defaultdict(list)
    tickets.sort(key=lambda x: x[1], reverse=True)

    for _from, _to in tickets:
        dic[_from].append(_to)

    def dfs(result):
        if len(result) == len(tickets) + 1:
            return result
        while dic[result[-1]]:
            city = dic[result[-1]].pop()
            res = dfs(result + [city])
            if res:
                return res
            dic[result[-1]].append(city)
        return None

    return dfs(["JFK"])

• Leetcode를 통과하는 코드를 작성하지 못함
• 같은 노드를 재방문 할 수 있고, 간선을 모두 소비해야하는 오일러 경로 문제 타입을 기억해놔야겠다