본문으로 건너뛰기

여행 경로 찾기 해설

여행 경로 찾기 해설

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

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


함수 구현

  1. 그래프 초기화:

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

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

  2. 티켓 정렬:

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

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

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

  4. 최종 경로 계산:

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

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


모범 답안
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] # 최종 경로 반환

사용 예시

입출력 예시
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"에 도착하는 경로가 생성됩니다. 이 경로는 주어진 조건을 만족하므로, 함수는 이 경로를 반환합니다.