[Programmers] 여행경로

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

프로그래머스

난이도: Lv.3

권장 시간: 20분

권장 시간 복잡도:

문제 설명

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

---

제한사항

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

---

입출력 예

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

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

---

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만,
["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]가 알파벳 순으로 앞서므로 이를 반환합니다.

---

from collections import defaultdict

def solution(tickets):
    # 티켓 목록을 기반으로 각 공항에서 연결된 공항 목록을 저장할 그래프 생성
    graph = defaultdict(list)
    for ticket in tickets:
        # 티켓의 출발 공항(ticket[0])에 도착 공항(ticket[1])을 추가
        graph[ticket[0]].append(ticket[1])

    # 각 공항에서 연결된 도착지들을 알파벳 순으로 정렬
    for key in graph:
        graph[key].sort()

    # 경로를 저장할 리스트
    routes = []

    # DFS로 경로를 탐색하는 함수
    def dfs(route):
        # 경로의 길이가 모든 티켓을 사용한 경우 (len(tickets) + 1개의 공항을 지나야 함)
        if len(route) == len(tickets) + 1:
            # 유효한 경로가 되면 routes 리스트에 추가
            routes.append(route)
            return  # 경로를 찾았으면 더 이상 탐색할 필요 없음

        # 현재 공항(route[-1])에서 갈 수 있는 모든 도착지로 DFS 재귀 호출
        for i, arrive in enumerate(graph[route[-1]]):
            # 현재 공항에서 갈 수 있는 공항(arrive)로 가는 경로를 임시로 추가
            temp = route[:]
            temp.append(arrive)

            # 해당 도착지(arrive)를 사용한 티켓을 그래프에서 제거 (방문 처리)
            graph[route[-1]].pop(i)

            # 재귀적으로 다음 경로 탐색
            dfs(temp)

            # 복구 처리: 방문한 티켓을 다시 원래대로 복원
            graph[route[-1]].insert(i, arrive)

    # DFS를 "ICN"에서 시작하여 모든 경로를 탐색
    dfs(["ICN"])

    # 찾은 첫 번째 경로를 반환 (알파벳 순으로 탐색되므로 첫 번째가 정답)
    print(routes[0])  # 디버깅용 출력
    return routes[0]

---