티켓으로 여행 경로 만들기: BFS

<제한사항>

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

from collections import deque
 
def solution(tickets):
    answer = []
    graph = dict() # 출발 공항: 도착 가능한 공항
 
    # 방문 가능한 공항 그래프 생성
    for d, a in tickets:
        graph[d] = graph.get(d, []) + [a]   # key=d에 아무것도 없으면 list 반환
 
    data = deque() # (출발 공항, 방문한 경로 list, 남은 티켓)
    data.append(("ICN", ["ICN"], tickets.copy()))   # 초기값
    
    while data:
        departure, path, ticket = data.popleft()
 
        if not ticket: # 주어진 티켓을 모두 사용한 경우
            answer.append(path)
        else:
            if departure not in graph.keys(): # 갈 수 있는 공항이 없는 경우
                # ["ICN", "ATL"], ["ICN", "SFO"]일 때, 최종 목적지가 SFO로 가야하는데 
                # SFO가 먼저 처리될 경우 continue를 이용하여 ATL로 접근
                continue

            for arrival in graph[departure]:
                if [departure, arrival] in ticket: # 가는 항공권이 있는 경우
                    nextTicket = ticket.copy()
                    nextTicket.remove([departure, arrival]) # ticket 사용
                    data.append((arrival, path + [arrival], nextTicket))
    
    return sorted(answer)[0]