프로그래머스 - 여행경로 [파이썬]

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

프로그래머스

---

풀이 과정

ICN에서 시작해 주어진 비행기 표를 모두 사용하는 여행 경로를 짜는 문제이다. 가능한 경로가 여러개라면 사전식으로 앞선 경로를 답으로 내야 한다.

 

모든 도시를 방문할 수 없는 입력은 들어오지 않으므로 모든 도시를 DFS로 방문하면 된다. 비행기 표를 defaultdict에 담아놓는데, pop으로 비행기표를 꺼내면서 알파벳 순이 앞선 도시를 먼저 방문하기 위해 티켓 리스트를 도착지를 기준으로 알파벳 내림차순으로 정렬해놓고 defaultdict에 담았다.

 

https://greentea31.tistory.com/202

LeetCode - 332. Reconstruct Itinerary [Python]

LeetCode의 332번 문제와 아주 유사한 문제이고 풀이도 유사하게 하면 된다.

 

---

소스 코드

import collections

def solution(tickets):
    answer = []
    ticket_list = collections.defaultdict(list)
    tickets.sort(key=lambda x: x[1], reverse=True)
    
    for depart, arrive in tickets:
        ticket_list[depart].append(arrive)
    
    print(ticket_list)
        
    def dfs(go):
        while ticket_list[go]:
            dfs(ticket_list[go].pop())
        answer.append(go)  # 재귀를 사용해 여행순서가 반대 순서대로 answer에 저장된다.
        
    dfs('ICN')
    return answer[::-1]  # 그래서 반대로 출력해주어야 한다.