문제

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 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예시

아이디어

👎 맨 처음은 "ICN"으로 시작하므로 우선 answer에 추가한다.
tickets이 비어있을 때까지 반복하면서 answer의 마지막과 비교를 한다. 비교를 하면서 여러개인 경우 정렬을 해야하기 때문에 tmp에 담아두고 tickets에서 삭제하고, answer에 추가한다.

✅ 런타임 에러가 난 이유
예를 들어, [["ICN", "AAA"], ["ICN", "BBB"], ["BBB", "ICN"]] 입력의 경우 내 풀이대로 하면 answer = ["ICN", "AAA"]가 되어 더 이상 진행할 수 없게 된다. answer = ["ICN", "BBB", "ICN", "AAA"]가 되도록 만들어야 한다.

[#Error] solution함수_python

:: 런타임 에러

def solution(tickets):
    answer = ["ICN"]

    while tickets != []:
        tmp = []
        for i in range(len(tickets)):
            if tickets[i][0] == answer[-1]:
                tmp.append(tickets[i][1])
        tmp.sort()
        tickets.remove([answer[-1],tmp[0]])
        answer.append(tmp[0])
    return answer

[#Clone] solution함수_python

아이디어 참조

✅ 1. 각 출발지에서 갈 수 있는 도착지를 딕셔너리 형태로 저장한 후, 반대로 정렬한다.
2. stack의 맨 마지막 원소를 가져와서 routes에 있으면 routes에서 제거하여 stack에 추가한다.
3. 맨 마지막 원소가 routes에 없으면(더 이상 이동할 수 없음) path에 넣는다.
4. path에는 경로가 반대로 나오므로 뒤집어서 출력한다.

[["ICN", "AAA"], ["ICN", "BBB"], ["BBB", "ICN"]]인 경우,

stack	path
["ICN"]	[]
["ICN", "AAA"]	[]
["ICN"]	["AAA"]
["ICN", "BBB"]	["AAA"]
["ICN", "BBB", "ICN"]	["AAA"]
["ICN", "BBB"]	["AAA", "ICN"]
["ICN"]	["AAA", "ICN", "BBB"]
[]	["AAA", "ICN", "BBB", "ICN"]

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]	#t[0]이 없으면 [], default 값
    for r in routes:
        routes[r].sort(reverse=True)
    stack = ['ICN']
    path = []
    while stack:
        top = stack[-1]
        if top in routes and routes[top]:
            stack.append(routes[top].pop())
        else:
            path.append(stack.pop())
    return path[::-1]

clone함수 출처