[프로그래머스] 여행경로 _ 파이썬

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

1차 시도 (테케 1, 2 시간 초과)

일단 그냥 풀어본 방법.
문제는 모든 티켓을 다 사용하지 못했는데 갈 곳이 끊겼을 때.
이걸 고려하지 않고 그냥 코드를 짜서 실패.

def solution(tickets):
    answer = ['ICN']
    check = [True] * len(tickets)
    depart = 'ICN'
    idx = 0
    
    while True in check:
        arrival = 'XXX'
        arr_idx = 0
        for i in range(len(tickets)):
            if check[i] and tickets[i][0] == depart and tickets[i][1] < arrival:
                    arrival = tickets[i][1]
                    arr_idx = i
                    
        answer.append(arrival)
        check[arr_idx] = False
        depart = arrival
    
    return answer

2차 시도 (다른 분 풀이 참고)

DFS로 풀어보려 했는데 도저히 중간에 갈 곳이 끊겼을 때 대처법이 생각이 안남.
키 포인트는 갈 곳이 없다는 것 == 마지막 종착지라는 것
그래서 마지막 종착지부터 answer에 삽입하면 해결 가능.

1. routes : key가 출발지, value가 도착지인 dict
2. routes의 key(출발지)를 내림차순으로 정렬 -> 스택이 LIFO 이므로 알파벳이 뒷쪽일 수록 먼저 스택에 넣기 위해서
3. 첫 출발지 'ICN'이 포함된 스택 생성
4. 스택에 남은 곳이 없을 때까지 while 문 돌리기
5. 스택 맨 위에 있는 지역이 출발지로, depart에 저장.
6. depart가 아예 dict의 key(출발지)에 없거나, depart의 도착지들이 이미 다 거쳐가서 비어 있다. == 마지막 도착지다.
   따라서 스택에서 pop하고 answer에 저장.
7. depart에서 출발하는 티켓이 routes에 있다면 pop하고 스택에 저장.

def solution(tickets):
    answer = []
    routes = {route[0]:[] for route in tickets}
    for start, end in tickets:
        routes[start].append(end)
    
    for r in routes.keys():
        routes[r].sort(reverse=True)
        
    stack = ['ICN']
    
    while stack:
        depart = stack[-1]
        if (depart not in routes) or (not len(routes[depart])):
            answer.append(stack.pop())
        else:
            stack.append(routes[depart].pop())
            
    answer.reverse()
    
    return answer