[프로그래머스 Lv.3] 여행경로 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

풀이

DFS를 활용한 문제이다. dictionary를 활용하여 전체 티켓들을 사용해 마치 graph와 같은 구조를 완성하고, 이를 DFS로 순회하면 된다. DFS로 순회하며, 더 이상 이동할 수 없는 경우가 되면 그 때 위치하는 공항을 answer 배열에 저장한다.

다만 주의해야할 점이 있는데, 가능한 경로가 2개 이상일 땐 알파벳 경로가 앞서는 경우를 반환하라고 했기 때문에 그래프를 완성할 때 정렬이 필요하다는 점을 고려하며 구현해야 한다.

from collections import defaultdict

def solution(tickets):
    answer = []
    
    routes = defaultdict(list)
    for ticket in tickets: # 전체 티켓들을 순회하며
        depart, arrive = ticket
        routes[depart].append(arrive) # 그래프를 만들기
    
    for route in routes.values():
        route.sort(reverse=True) # 알파벳 순으로 그래프에서 pop하기 위해 알파벳의 역순으로 정렬 (pop은 배열의 뒤에서부터 데이터를 꺼냄)
            
    def dfs(airport):
        while routes[airport]: # 다음 공항이 존재하면
            next_dep = routes[airport].pop()
            dfs(next_dep) # 다음 공항부터 이어서 DFS 수행
        else:
            answer.append(airport) # 더 이상 이동할 공항이 없으면 answer 배열에 저장
    
    dfs("ICN") # 인천 공항부터 시작
    
    return answer[::-1] # 더 이상 이동할 수 없는, 마지막 공항부터 배열에 넣었기 때문에 거꾸로 정렬하여 반환