[프로그래머스] 여행경로

문제

 

풀이

1. 주어진 항공권을 도착지를 기준으로 정렬합니다.

2. 항공권 정보를 그래프로 변환합니다.

3. "ICN"에서 시작하여 DFS (깊이 우선 탐색)을 수행하여 경로를 찾습니다.

 

 

파이썬을 공부하면서 풀어서 정렬하는 방법에 대해서 새롭게 알게 되었습니다.

다음에 기회가 되면 더 자세히 정리하겠지만 간단하게 살펴보겠습니다.

 

항공권을 도착지 기준으로 오름차순 정렬을 해야해서 아래와 같이 sorted() 내장함수를 이용했습니다.

sorted(tickets, key=lambda x: x[1])

• key 매개변수는 정렬 기준을 지정하는 데 사용되며, 여기에는 함수가 전달됩니다.
• lambda는 파이썬에서 익명 함수를 정의하는 키워드입니다. 익명 함수는 이름 없이 정의되는 간단한 함수입니다.
  • x는 lambda 함수의 매개변수입니다. 여기서 x는 tickets의 각 요소 (즉, 각 항공권)를 나타냅니다.
  • x[1]은 x의 두 번째 요소를 나타냅니다. tickets의 각 항공권은 2개의 문자열로 구성된 리스트이므로, x[1]은 도착지를 나타냅니다.
    • x[1]은 ["ICN", "JFK"] 인 경우, JFK를 의미합니다.

 

 

 

코드

import collections

def solution(tickets):
    graph = collections.defaultdict(list)
    
    for a, b in sorted(tickets, key=lambda x: x[1]):
        graph[a].append(b)
    
    route = []

    def dfs(start):
        while graph[start]:
            dfs(graph[start].pop(0))
        route.append(start)

    dfs("ICN")
    return route[::-1]

 

 

시간복잡도는  O(n log n) 입니다.

우선 항공권을 정렬하는 데 O(n log n)의 시간이 소요됩니다.

그리고 dfs() 함수를 실행하는 데 O(n)의 시간이 소요됩니다. 각 항공권에 대해 최대 한 번 호출됩니다. 따라서 재귀 호출의 최대 횟수는 항공권의 수와 동일하므로 O(n)입니다.  각 출발지에 대한 도착지 리스트에서 항목을 pop하는 작업은 해당 출발지의 항공권 수만큼 수행됩니다. 모든 출발지에 대해 항공권은 한 번만 pop되므로, 전체적으로 항공권의 수만큼 작업이 수행됩니다. 따라서 O(n)입니다.

그러므로 시간복잡도는  O(n log n) 입니다.

 

참고

• 여행경로