[アルゴリズム解答]旅行コース

問題の説明

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

せいげんじょうけん

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

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

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

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

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

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

I/O例

I/O例説明

例1

ICN JFK HND IAD]順にアクセス可能

例2

ICN、SFO、ATL、ICN、ATL、SFOの順でアクセスできますが、[ICN、ATL、ICN、SFO、ATL、SFO]のアルファベット順でリードしています.

に答える

import copy

def _search(left_tickets, ticket_history, result):
    for ticket in left_tickets:
        if ticket_history[-1][1] == ticket[0]:
            if len(left_tickets) > 1:
                added_history = copy.deepcopy(ticket_history)
                added_history.append(ticket)
                _search(copy.deepcopy([x for x in left_tickets if x is not ticket])
                                , added_history
                                , result)
            elif len(left_tickets) == 1:
                ticket_history.append(ticket)
                result.append(ticket_history)


def solution(tickets):
    answer = []
    result = []
    for ticket in tickets:
        if ticket[0] == 'ICN':
            left_tickets = copy.deepcopy([x for x in tickets if x is not ticket])
            _search(left_tickets, [ticket], result)
    
    for seq in result:
        path = []
        for index, ticket in enumerate(seq):
            if index == 0:
                path.extend(ticket)
            else:
                path.append(ticket[1])
        answer.append(path)
    
    answer = sorted(answer, key = lambda x: x)
    
    return answer[0]

  _search(left_tickets, ticket_history, result)は、solution(tickets)の内部から呼び出される関数である.深度優先検索で可能なすべてのパスを見つけます.因子は以下の通りである.
left tickets:未使用のチケットリスト
ticket history:これまでのパス
≪結果｜Results｜ldap≫:すべてのチケットが使用されている場合、可能なすべてのパスのリストが格納されます.solutionのうち、「ICN」からのチケットのみを起点として_searchを呼ぶ.
  _searchでは、最後のパスの到着点と残りのチケットの出発地を確認し、2つの位置が同じであればticket historyとleft ticketsにそれぞれ追加、削除し、再び_searchを呼び出す.この場合、残りのチケットがチケットのみの場合、チケットhistoryにチケットを追加し、resultにチケットhistoryを追加します.上記の手順でresultに可能なすべてのパスを追加します.
  _searchの再帰呼び出しがすべて終了した後、結果をsolutionで確認し、一連のパスに変換する.次に、アルファベット順に並べ替えて、最初の要素を返します.