학습 주제
DFS 이용한 여행경로 문제 파이썬 코드로 풀기.

학습 내용

사전을 이용하여, 각 공항에서 갈 수 있는 항공권의 집합을 저장함. (접근이 다른 자료구조에 비해 용이함)
출발지: key
도착지: value

항공권을 사용하면, value를 삭제

갈 수 있는 방향이 여러개일 경우, 알파벳 순서로 빠른 쪽을 출발. 이 때 value가 되는 도착지의 목록을 리스트로 표현함. 순서를 집어넣어야 하기 때문. 리스트의 경우 앞에서 제거하는 것보다, 뒤에서 제거하는 것이 편함. 따라서

알파벳의 역순으로 정렬

복잡도

모든 목적지에 해당하는 표가 스택에 한번씩 들어가고, 스택에서 한번씩 꺼내짐.
리스트에 맨 끝에있는 것을 꺼냄.(정렬되어 있음)

for r in routes:
	routes[r].sort(reverse=True)

O(NlogN)

while len(stack) >0:
복잡도는 O(n) 이미 정렬되어 있기 때문.

구현 코드

def solution(tickets):
    routes = {}
    for t in tickets:
        # 앞이 출발공항, 뒤가 도착공항
        # 초기화, 있을 경우 추가로 extend
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
    # routes 딕셔너리의 키들을 순회
    for r in routes:
        routes[r].sort(reverse = True)
    # 인천공항이 무조건 시작하므로, 넣고 시작
    stack = ["ICN"]
    # 갈려는 경로, 어느어느 공항을 거치는지
    path = []
    # 재귀적 알고리즘의 기초
    while len(stack) > 0:
        top = stack[-1]
        # 어떤 공항에서 출발하는 표가 한장도 없다면, 있기는 있으나 다 소진하여 없게 된다면.
        if top not in routes or len(routes[top]) == 0:
            path.append(stack.pop())
        # 갈 수 있는 공항이 있으면,
        else:
            # 알파벳 역순 정렬이기에, 가장 앞서는 공항 선택
            stack.append(routes[top][-1])
            # 또는 value가 리스트형이기에 pop을 적용해도 됨.
            routes[top] = routes[top][:-1]

    # path엔 역순으로 저장되어 있기 때문에.
    return path[::-1]