여행 경로 찾기 해설

비행 티켓들로 가능한 여행 경로를 찾는 함수를 작성합니다.

이 과정은 재귀 호출과 깊이 우선 탐색(DFS)을 사용하여 구현됩니다.

1. 그래프 초기화:

   • 각 티켓의 출발지와 목적지를 사용하여 그래프를 생성합니다.

   • 이 그래프는 각 공항에서 출발하여 도달할 수 있는 모든 목적지를 리스트로 저장합니다.

2. 티켓 정렬:

   • 각 공항에서 출발하는 티켓들을 역순으로 정렬합니다. 이렇게 하면 DFS 탐색 시 알파벳 순으로 가장 빠른 경로를 우선적으로 탐색합니다.

3. DFS 함수 구현:

   • 재귀 함수 dfs를 정의합니다. 이 함수는 현재 공항에서 출발하여 가능한 모든 경로를 탐색합니다.

   • 탐색이 끝난 후에는 경로를 route 리스트에 추가합니다.

4. 최종 경로 계산:

   • ICN 공항에서 시작하여 dfs 함수를 호출합니다.

   • 경로는 역순으로 저장되므로, 최종 결과를 반환하기 전에 리스트를 뒤집습니다.

Copy
def solution(tickets):
    graph = {}  # 그래프 초기화
    for start, end in tickets:
        graph.setdefault(start, []).append(end)  # 출발지와 목적지 쌍 추가
        graph.setdefault(end, [])

    # 티켓 정렬
    for airport in graph:
        graph[airport].sort(reverse=True)

    route = []  # 경로 저장

    # DFS 함수
    def dfs(airport):
        while graph[airport]:
            dfs(graph[airport].pop())  # 다음 목적지로 이동
        route.append(airport)  # 경로에 추가

    dfs("ICN")  # 'ICN'에서 시작
    return route[::-1]  # 최종 경로 반환

Copy
print(solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]))  # 출력: ["ICN", "JFK", "HND", "IAD"]

이 예시에서 주어진 티켓들을 이용하여 가능한 여행 경로를 구하는 문제입니다. 티켓은 ["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]로, 각각 출발지와 목적지를 나타냅니다. 이 티켓들을 이용하여 가능한 모든 경로 중 알파벳 순으로 가장 빠른 경로를 찾습니다.

함수 solution은 이 티켓들을 통해 다음과 같은 경로를 찾습니다: ["ICN", "JFK", "HND", "IAD"]. 이 경로는 모든 티켓을 사용하며, 가능한 경로 중 알파벳 순서로 가장 빠릅니다.

"ICN"에서 출발하여 "JFK"로 가고, 그 다음 "HND"로 가서 마지막으로 "IAD"에 도착하는 경로가 생성됩니다. 이 경로는 주어진 조건을 만족하므로, 함수는 이 경로를 반환합니다.