from collections import defaultdict
import bisect
def solution(tickets):
graph = defaultdict(list)
for v1, v2 in tickets :
bisect.insort_left(graph[v1], v2)
stack = ['ICN']
visited = []
while stack :
airport = stack[-1]
if graph[airport] :
stack.append(graph[airport].pop(0))
else :
visited.append(stack.pop())
return visited[::-1]
풀이
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
비행장의 다음경로(자식)들의 리스트는 알파벳 순서를 유지해야합니다.
graph = defaultdict(list)
for v1, v2 in tickets :
bisect.insort_left(graph[v1], v2)
bisect를 이용해 넣으면서 자동으로 자식들의 알파벳 순서가 유지되도록 한 뒤, DFS로 자식없는 놈이 나올 때 까지 자식을 뽑고 방문하고를 반복.