問題の説明

与えられたすべての航空券を利用して旅行ルートを作りたいです.いつも「ICN」空港から
航空券情報を含む2次元配列航空券をパラメータとして指定する場合は、アクセスした空港経路をレイアウトに入れて返します.

せいげんじょうけん

すべての空港はアルファベットの大文字の3文字で構成されています.

所定の空港数は3つ以上10000個以下である.

切符の各行[a,b]は、a空港からb空港までの航空券があることを示す.

の航空券はすべて使用します.

可能なパスが2つ以上ある場合は、アルファベット順にリードするパスを返します.

すべての都市へのアクセスは許可されていません.

I/O例

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

I/O例説明
例1["ICN", "JFK", "HND", "IAD"]の順序でアクセスできます.
例2["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"]の順でアクセスすることもできますが、["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]はアルファベット順でリードしています.

方法

この問題は深い探索を経て解決された.まずramdaを使用してticketを到着地のアルファベット順に並べ替え、次の目的地を格納するためにディックシーケンス図を生成します.これで目的地をアルファベット順に選択できます.そして、この問題では、すべてのチケットを使うことが重要なポイントなので、その目的地に行ったら、すべてのチケットが使えないので、再び戻らなければなりません.したがって、深度優先探索では、現在のパスリストの長さとチケットの長さ+1が等しい場合にのみ、戻りパスリストが記述される.
lambdaを用いて

枚のチケットをx[1]を基準に昇順ソートした.

グラフを使用したグラフィックは、ディクシャナとして宣言されます.

枚のチケットのfrm、toのゲートを巡ります.
->graph[frm]にtoを加えます.

dfs関数をcurとして宣言し、結果をパラメータとして使用します.
->結果の長さがチケットの長さ+1に等しい場合、
-->結果を返します.
->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の場合は、他の場合にチケットを使用するために再読み込みしてください)

の回答をdfs('ICN', ['ICN'])に保存します.

の答えを返します.

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