프로그래머스 - 여행경로 파이썬 (DFS)

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

코딩테스트 연습 - 여행경로

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

문제 풀이

일일히 하나씩 비교하는 방식으로 풀어봤는데, 그렇게 하니까 중복된 여행 경로가 있을 때 처리하기가 어려워서 다른 사람들의 풀이를 참고했다!

dfs 를 써야하나 했는데 스택을 쓰니까 엄청 짧은 코드로 해결할 수 있는 문제였다.

1. tickets 배열을
   { 출발지: [목적지1, 목적지2,,] }
   이런 식으로 된 딕셔너리 형태로 바꿔준다.
2. dict 의 각 출발지별 목적지 배열을 역순으로 정렬해준다.
   (목적지 배열의 뒤부터 stack에 들어가기 때문에, 역순으로 정렬하면 스택의 앞쪽을 시작점으로 하게 됨)
   ICN 이 스택의 가장 아래에 위치하기 때문에
3. 출발지는 무조건 'ICN' 이어야 하기 때문에 스택에 'ICN' 을 넣어준다.
4. stack 의 top (제일 마지막에 추가된 원소)을 꺼내서, dict 에서 top 을 출발지점으로 했을 때 목적지 배열 중 가장 뒤에 있는 원소를 꺼내서 stack에 추가한다.
5. top 으로 시작하는 여행 경로가 dict 에 없을 경우, stack 의 top 을 꺼내서 answer 에 넣어준다.
6. stack 에 원소가 다 없어질때까지 4-5번을 반복

from collections import defaultdict

def solution(tickets):
    answer = []
    path = defaultdict(list)
    for ticket in tickets:
        path[ticket[0]].append(ticket[1])
    for key in path.keys():
        path[key].sort(reverse=True)
    print(path)
    stack = ['ICN']
    while stack:
        top = stack[-1]
        if not path[top]:
            answer.append(stack.pop())
        else:
            stack.append(path[top].pop())
    print(stack)
    answer.reverse()
    return answer