문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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

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

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

접근 방법

이번 문제는 깊이우선탐색으로 해결하였다. 우선 람다를 사용하여 ticket을 도착지의 알파벳 순으로 정렬한 후에 그래프를 딕셔너리로 생성하여 다음 목적지들을 저장한다. 이렇게 하면 알파벳순으로 목적지를 선택할 수 있게 된다. 그리고 이 문제에서는 모든 티켓을 모두 사용하는 것이 중요한 포인트이기 때문에 해당 목적지로 갔을 때의 경우에 모든 티켓을 사용할 수 없게 된다면 다시 되돌아와야 한다. 그래서 깊이우선탐색에서 현재 경로 리스트의 길이와 티켓의 길이+1이 같을 경우에만 경로 리스트를 반환하도록 작성하였다.

• tickets를 lambda를 이용하여 x[1]을 기준으로 오름차순 정렬한다.
• 그래프로 사용할 graph를 딕셔너리로 선언한다.
• tickets를 순회하는 frm, to에 대한 for문을 돌린다.
  -> graph[frm]에 to를 넣는다.
• dfs 함수를 cur, results를 인자로 갖도록 선언한다.
  -> 만약 results의 길이가 tickets의 길이+1과 같을 경우,
  --> results를 반환한다.
  -> enumerate(graph[cur])을 순회하는 i, nxt에 대한 for문을 돌린다.
  --> graph[cur]에서 i번째 원소를 지운다.
  --> n_results를 result[:]로 저장한다. (복사를 위해 [:]을 붙임)
  --> n_results에 nxt를 넣는다.
  --> ans를 dfs(nxt, n_results)로 저장한다.
  --> 만약 ans가 True일 경우, ans를 반환한다.
  --> graph[cur]의 i 인덱스에 nxt를 넣는다. (False일 경우 다시 넣어서 다른 경우에 티켓을 사용)
• answer를 dfs('ICN', ['ICN'])으로 저장한다.
• answer를 반환한다.

solution.py

import collections
def solution(tickets):
    tickets.sort(key=lambda x: x[1])
    graph=collections.defaultdict(list)
    for frm, to in tickets:
        graph[frm].append(to)
    def dfs(cur, results):
        if len(results)==len(tickets)+1:
            return results
        for i, nxt in enumerate(graph[cur]):
            graph[cur].pop(i)
            n_results=results[:]
            n_results.append(nxt)
            ans=dfs(nxt, n_results)
            if ans:
                return ans
            graph[cur].insert(i, nxt)
    answer=dfs('ICN', ['ICN'])
    return answer