220523 - 여행 경로

◾ 여행 경로 : 프로그래머스 LEVEL 3

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

출력

• 방문하는 공항 경로

입출력 예

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"]

---

◾ 풀이

1. 해설

• 참고 : https://wwlee94.github.io/category/algorithm/bfs-dfs/travel-route/
• 스택을 활용한 DFS로 해결할 수 있다.
• 이동 가능한 루트를 정렬하고 차례로 스택에 추가한다.
• 더이상 이동 불가능한 지역일 경우 answer에 추가한다.
  • 이동 불가능 지역 : 모든 티켓을 사용한 지역
• append를 통해 추가하므로 answer에는 정답이 역순으로 되어있음을 주의해야한다.

---

2. 프로그램

1. 티켓 routes 정리
2. 각 공항에 대한 도착지 정렬(내림차순)
3. stack 초기화 : ICN
4. 마지막 지역 기준으로 다음 이동 가능 지역 탐색
   • 이동 가능한 경우 : 사전순으로 가장 빠른 지역 추가
   • 이동 불가능한 경우 : answer에 해당 지역 추가
5. stack이 빌 때까지 위 작업 반복

# 코드
from collections import deque
def solution(tickets):
    answer = []

    routes = {} # 루트를 담을 딕셔너리
    for start, end in tickets:
        # start, end에 대해 초기화
        # 'des' : 이동 가능한 공항
        # 'count' : 이동 가능한 남은 공항의 수
        if start not in routes:
            routes[start] = {'des' : [], 'count' : 0}
        if end not in routes:
            routes[end] = {'des' : [], 'count' : 0}
        # 루트 추가
        routes[start]['des'].append(end)
        routes[start]['count'] += 1
    
    # 각 공항에 대해 'des'를 내림차순 정렬
    # 이후 pop() 명령을 조금이라도 빠르게 실행하도록 하기 위함
    for key in routes.keys():
        routes[key]['des'].sort(reverse=True)

    # 스택을 활용한 DFS
    #   사전순으로 추가하며 더이상 추가할 수 없을 때
    #   차례로 정답 경로에 추가(티켓이 더이상 없을 때)
    stack = ["ICN"]
    while stack:
        start = stack[-1]
        # 더이상 이동할 티켓이 없는 지역은 answer에 추가
        if routes[start]['count'] == 0:
            answer.append(stack.pop())
        # 사전순으로 차례대로 stack에 추가
        else:
            stack.append(routes[start]['des'].pop())
            routes[start]['count'] -= 1
    
    return answer[::-1]