[DFS/BFS] 여행경로

여행경로

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

☘️ 풀이

#dfs 
from collections import defaultdict
def solution(tickets):
    r = defaultdict(list) # {}
    
    for i,j in tickets:
        print(i,j)
        r[i].append(j) # i가 key, j가 value 
        print(r)
    for i in r.keys():
        
        r[i].sort() # value 정렬
        print("구분선")
        print(r[i], r)
    s = ["ICN"]
    p = []
    while s:
        q = s[-1]
        print(q)
        if r[q] != []:
            s.append(r[q].pop(0)) # 첫번째 원소 제거
        else:
            p.append(s.pop()) # 마지막 원소 제거 
    return p[::-1] # 역순 

#dfs 
# 알파벳 내림차순
# 경로 실패시 재경로 (모든 도시를 방문할 수 없는 경우x)
# insert로 정확한 위치로 복구 
def solution(tickets):
    airports = {}  # key: 출발 공항, value: 도착할 수 있는 공항들의 리스트

    for start, end in tickets:
        if start not in airports:
            airports[start] = []
        airports[start].append(end)
    #print(airports)
    # 알파벳 역순으로 정렬
    for key in airports:
        airports[key].sort(reverse=True)
    #print(airports)
    
    total_tickets = len(tickets)
    current_path = []
    
    dfs(airports, total_tickets, current_path, "ICN", 0)
    
    return current_path

def dfs(airports, total_tickets, current_path, current_airport, used_tickets):
    
    
    # 현재 공항을 경로에 추가
    current_path.append(current_airport)
    
    # 모든 티켓을 사용했다면 종료
    if used_tickets == total_tickets: #빙문여부 대신 
        #print(current_airport, "티켓 다 사용")
        return True
    
    if current_airport not in airports: # 경로 실패시 재경로
        current_path.pop()
        return False
    
    # 현재 공항에서 이동할 수 있는 다음 공항들을 순회
    for idx in range(len(airports[current_airport])):
        next_airport = airports[current_airport].pop()  # 마지막 요소 선택
        #print(next_airport)
        
        # 다음 공항으로 이동할 수 있다면
        if dfs(airports, total_tickets, current_path, next_airport, used_tickets + 1):
            return True
        
        # 실패했을 경우 원래대로 복구
        airports[current_airport].insert(0, next_airport)
        #next_airport라는 값을 리스트의 맨 앞쪽(인덱스 0)에 추가
    
    # 모든 경로를 탐색했지만 실패했을 경우 경로에서 현재 공항 제거
    current_path.pop()
    return False

# solution_2 우선순위 큐 적용
from collections import defaultdict
import heapq

def solution(tickets):
   graph = defaultdict(list) # 기본값 list 

   # 우선순위 큐 사용을 위해 티켓들을 역순으로 넣어준다.
   for start, end in sorted(tickets, reverse=True):
       graph[start].append(end)
   
   path = []
   stack = ["ICN"]
   print(graph)
   while stack:
       top = stack[-1]

       # 현재 위치에서 갈 수 있는 다음 목적지가 있으면
       if graph[top]:
           stack.append(graph[top].pop())
       else:
           path.append(stack.pop())

   
   return path[::-1]  # 역순으로 반환

TIL

🌳 defaultdict

일반적인 딕셔너리와 비슷하지만, 딕셔너리에 키가 없을 때 기본값을 반환

from collections import defaultdict
my_dict = {}
print(my_dict['key'])  # KeyError: 'key' not in dictionary


my_dict = defaultdict(int)
print(my_dict['key'])  # Output: 0 (int의 기본값)