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

🧑🏻‍💻 문제링크

문제풀이

출발지와 도착지가 주어졌을 때 방문하는 공항경로를 구하는 문제이다. 기존의 DFS 알고리즘을 for문으로 돌려서 풀었는데 while문으로도 저렇게 구할 수 있다는 것을 알 수 있었다. 그리고 문제를 defaultdict을 이용해서 풀면 더 간단하다는 것을 배울 수 있었다. (세상엔 재능 있는 분들이 너무 많아...🥲)

다시 생각해볼 수 있었던 점은 2차원 배열을 파이썬 내장 함수로 정렬을 할 때

arr = [['b', 'c'], ['a', 'z']]
print(sorted(arr))

이런 식으로 주어져 있으면 각 0번째 인덱스를 기준으로 먼저 정렬을 하고 그 다음에 1번째 인덱스 순으로 정렬을 한다는 것이었다.

코드

from collections import defaultdict
        
def solution(tickets):
    answer = []
    graph = defaultdict(list)

    # 출발지 : 도착지 딕셔너리로 만듬(알파벳순)
    for dept, arr in sorted(tickets):
        graph[dept].append(arr)

    # DFS 방식
    def DFS(dept):
        while graph[dept]:
            DFS(graph[dept].pop(0))
        answer.append(dept)

    DFS("ICN")

    return answer[::-1]

결과