https://programmers.co.kr/learn/courses/30/lessons/43164
https://leetcode.com/problems/reconstruct-itinerary/
리트코드에서 동일한 문제를 푼 적이 있어서 같은 방법으로 풀었다.
collections 모듈
을 이용해서 딕셔너리 그래프에 값이 없을때도 디폴트 값이 자동으로 할당되도록 해주었다.tickets
리스트를 정렬해주어서 문제 조건인 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 하도록 해주었다.route
리스트에 추가해준다.route
리스트에 거꾸로 정렬된 상태이다.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]