여행 경로

문제

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

문제 파악

모든 항공권을 사용해서 여행 경로를 짜는데, 알파벳 순으로 빠른 경로를 찾기
항상 “ICN”에서 출발

접근 방법

•	DFS(깊이 우선 탐색)로 모든 경로를 탐색
•	경로가 완성되면 리스트에 저장하고, 사전 순 정렬
•	티켓을 모두 사용했는지 체크하면서 백트래킹하기

문제 풀이

def solution(tickets):
    routes = []
    visited = [False] * len(tickets)

    def dfs(path, used):
        if len(used) == len(tickets):
            routes.append(path)
            return
        for i, (a, b) in enumerate(tickets):
            if not visited[i] and path[-1] == a:
                visited[i] = True
                dfs(path + [b], used + [i])
                visited[i] = False

    dfs(["ICN"], [])
    routes.sort()
    return routes[0]