프로그래머스 43164. 여행경로

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

프로그래머스

from collections import defaultdict

def solution(tickets):
    # 경로 그래프 생성
    link = defaultdict(list)
    for ticket in tickets:
        link[ticket[0]].append(ticket[1])
    
    # 각 출발지에서의 도착지들을 사전순 정렬
    for key in link:
        link[key].sort(reverse=True)  # 역순 정렬 (pop() 사용을 위해)
    
    ans = []  # 최종 경로를 저장할 리스트

    def dfs(start):
        while link[start]:  # 출발지에서 갈 수 있는 도착지가 남아 있다면
            next_dest = link[start].pop()  # 가장 사전순 경로 탐색
            dfs(next_dest)  # 다음 도착지로 이동
        ans.append(start)  # 더 이상 갈 곳이 없으면 현재 지점을 경로에 추가
    
    dfs('ICN')  # 시작점은 항상 'ICN'
    return ans[::-1]  # 경로를 역순으로 반환

시간복잡도 면에서 pop(0) 대신 pop()사용을 위해 역순으로 정렬하는 아이디어는 대단하다...

key값을 바로바로 생성해서 집어넣고 싶으면 defaultdict를 꼭 사용하기!