프로그래머스 여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164

dfs문제이다.
이 문제의 특징은 모든 지점을 한번씩 다 거쳐야 한다는 것이다.
그렇기 때문에 일반적인 dfs방식에서 모든 지점을 거치지 않았다면 해당 경로는 고려하지 않아야 한다.

어떤 티켓에 대해서 최종 목적지인 경우에는 그 티켓이 마지막에 와야한다.
그러므로 그 티켓부터 시작하여 역으로 찾아가는 방식을 택하였다.

역순으로 딕셔너리에 티켓을 담은 뒤, dfs를 돌면서 해당 티켓이 더이상 찾아갈 경로가 없다면 정답 배열에 넣어주었다. 만약 더 찾아갈 경로가 있다면 딕셔너리의 제일 마지막부분을 빼서 그 부분부터 다시 dfs를 돌도록 만들어 주었다

def solution(tickets):
    tickets.sort(reverse = True)
    d = {}
    for ticket in tickets:
        if ticket[0] in d:
            d[ticket[0]].append(ticket[1])
        else:
            d[ticket[0]] = [ticket[1]]
    start = ['ICN']
    answer = []
    while start:
        top = start[-1]
        if top not in d or len(d[top]) == 0: ## 더이상 갈 곳이 없다면
            answer.append(start.pop())
        else:
            top = d[top].pop()
            start.append(top)
    answer.reverse()
    return answer