[ Programmers 43164 ] 여행경로(Python)

문제

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

https://leetcode.com/problems/reconstruct-itinerary/
리트코드에서 동일한 문제를 푼 적이 있어서 같은 방법으로 풀었다.

문제 풀이

1. collections 모듈을 이용해서 딕셔너리 그래프에 값이 없을때도 디폴트 값이 자동으로 할당되도록 해주었다.
2. tickets 리스트를 정렬해주어서 문제 조건인 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 하도록 해주었다.
3. 시작 티켓인 ICN과 연결된 다른 티켓들을 모두 pop해서 dfs 함수에 다시 넣어준다.
4. 그리고 나서 시작 티켓을 route 리스트에 추가해준다.
5. dfs 함수가 끝나면 시작 티켓부터 목적지 티켓까지 route 리스트에 거꾸로 정렬된 상태이다.
6. 따라서 거꾸로 출력해주면 된다.

코드

import collections

def solution(tickets):
    graph = collections.defaultdict(list)

    for start,end in sorted(tickets):
        graph[start].append(end)

    route = []
    def dfs(ticket):
        while graph[ticket]:
            dfs(graph[ticket].pop(0))
        route.append(ticket)

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