(Python) 프로그래머스 - 여행경로

in Algorithm on Programmers, Level3

[문제 링크]

풀이

import heapq
from collections import defaultdict


def solution(tickets):
    answer = []
    way = defaultdict(list)

    for start, destination in tickets:
        if not way[start]:
            q = []
            heapq.heappush(q, destination)
            way[start] = q
        else:
            heapq.heappush(way[start], destination)

    stack = ["ICN"]
    while stack:
        start = way[stack[-1]]
        if not start:
            answer.append(stack.pop())
        else:
            stack.append(heapq.heappop(start))

    return answer[::-1]

defaultdict를 사용하면 dict 조건을 조건을 간소화 할 수 있다.
defaultdict을 선언할 때 인자로 list를 주었는데 이렇게 되면 없는 key값을 꺼내려고 하면 []를 반환해주고 키값만 넣어둔다면 []이 값으로 들어가 있다.
문제가 약간 이상한데 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로로 이동한다 했지만 주어진 항공권을 모두 사용할 수 없는 경우라면 알파벳 순서가 앞서는 경로로 이동하면 안된다.
따라서 일단 알파벳 순서로 모두 이동하는 경로를 stack에 담고 더이상 이동할 수 없다면 하나씩 pop하면서 사용하지 않은 항공권이 있는지 확인하여 있다면 다시 stack에 추가해준다.
즉, 알파벳 경로가 아니라 중간에 다른 경로를 갔다가 다시 돌아와서 알파벳 경로로 이동해야 했었다는 의미이다. 그 과정을 끼어넣어주는 것이다.
문제에서 모든 도시를 방문할 수 없는 경우는 주어지지 않는다고 하였으므로 분명 갔다가 다시 돌아올 것이다.

© 2021. By Backtony