[알고리즘] 일정 재구성

일정 재구성

내 풀이

def findItinerary(tickets: List[List[str]]) -> List[str]:
    graph = collections.defaultdict(list)
    result = []
    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])

    for key in graph.items():
        graph[key[0]].sort()

    def dfs(graph, start_point, path):
        if len(path) == len(tickets) :
            result.append(path[:] + [start_point])
            return result

        for dest in graph[start_point][:]:
            if len(result) > 0:
                break
            graph[start_point].remove(dest)
            dfs(graph, dest, path[:] + [start_point])
            graph[start_point].append(dest)

    dfs(graph, "JFK", [])
    return result[0]

여러 일정이 있을 경우 사전 어휘순으로 방문해야하므로, 그래프를 만들고 나서 정렬을 해준다. 하지만 무조건 사전 어휘순으로 방문하려고하면, 방법이 나오지 않을 수도 있다. 따라서 A에서 갈 수 있는 곳이 여러 곳 있을 때, 사전 어휘순으로 하나씩 시도해보아야한다.

책 풀이

def findItinerary(tickets: List[List[str]]) -> List[str]:
    graph = collections.defaultdict(list)
    # 그래프 순서대로 구성
    for a, b in sorted(tickets):
        graph[a].append(b)

    route = []
    def dfs(a):
        # 첫 번째 값을 읽어 어휘 순 방문
        print(a, route)
        while graph[a]:
            dfs(graph[a].pop(0))
        route.append(a)

    dfs('JFK')
    return route[::-1]

처음에는 코드를 보고

print(findItinerary([["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]))

같은 예제에서 에러가 나지 않을까 생각했다. 왜냐하면 JFK에서 알파벳 순에 따라 NRT가 아닌 KUL로 가버리면 다음 갈 곳이 없기 때문이다. 하지만 갈 곳이 없다는 것은 그것이 마지막이라는 것을 의미한다. 나중에 route[::-1]로 뒤집어주기 때문에 상관이 없다. 여기서 pop(0)는 큐의 연산이다. pop(0)는 O(n)인데, 애초에 값을 저장할 때 역순으로 저장해서 pop()을 해버리면 더 효율적이다. 코드는 아래와 같다.

책 풀이2

def findItinerary(tickets: List[List[str]]) -> List[str]:
    graph = collections.defaultdict(list)
    # 그래프 순서대로 구성
    for a, b in sorted(tickets, reverse = True):
        graph[a].append(b)

    print(graph)
    route = []
    def dfs(a):
        # 첫 번째 값을 읽어 어휘 순 방문
        print(a, route)
        while graph[a]:
            dfs(graph[a].pop())
        route.append(a)

    dfs('JFK')
    return route[::-1]