[プログラマー]旅行コース

[ソース]:https://programmers.co.kr

問題の説明

与えられたすべての航空券を利用して旅行ルートを作りたいです.いつも「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」の順が先です.

アクセスとコード

各空港をノードとし,与えられた航空券を幹線の情報とし,探索グラフと考えられる.
これは経路を求める問題で,DFSで求めるのが望ましいのでDFSで解く.
(A->Bまでのものがあれば、B->Cはこのようにして深さを優先的に検索する)
まずディックシャーナを用いてグラフを構成した.
このときdefaultdictを用いてvalueをリストに初期化する.(より便利){"ICN": ["자식노드1","자식노드2"]}これにより、グラフ情報が格納されます.
次に、dfsを使用してナビゲートするため、これらのサブノードリストをすべて逆ソートしました.
次のdfs図を見てください

[ソース]:https://velog.io/@vagabondms/DFS-vs-BFS
dfsはスタックを使用するため、リストに後ろのものが先に表示されます.
問題は、アクセスパスが複数である場合、アルファベット順に、前の優先順位をパスに表示させるべきであることです.
例えば、["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"]のような経路と["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] の2つの経路がある場合、後者はアルファベットでリードしているので、選択すべきである.
そこで,探索過程では,最初にアルファベット順の先頭者を選ぶために逆順に並べた.
この状態でdfsを用いて経路を解く.
通常、dfsを行うとスタックから1つポップアップされるが、この場合、その位置から出発するチケットが複数枚ある可能性があるため、この状況を確認する必要がある.
したがって、クエリがスタック内のpopではなく、最後の値である場合、その場所からのチケットがない場合、またはチケットが切れている場合(サブノードがない場合)、実行を続行できないことを示すため、パスに入れればよい.
次の場所へのテーブルがある場合は、次のナビゲーションのためにスタックに置くことができます.
これでパスを求めることができ、保存パスのリストでは、パスの後の値がリストの一番前に格納されます.
上にアップロードされたDFS図から見ると、6−5−2−4−3−1−0はこのように逆順序で記憶されている.
したがって、経路reverse()は、経路を反転させるために使用されるべきである.
次はコードです.

from collections import defaultdict


def dfs(start_node, graph):

    path = list()

    need_visited  = list()

    need_visited.append(start_node)

    while need_visited:
        current_node = need_visited[-1]

        #해당 위치에서 출발하는 티켓이 없던가, 티켓을 다사용한 경우(자식노드가 없는 경우)
        if current_node not in graph or len(graph[current_node]) == 0:
            #경로에 추가
            path.append(need_visited.pop())

        
        #다음 위치로 가는 표가 있으면
        else:
            need_visited.append(graph[current_node].pop())

    return path

def solution(tickets):

    #그래프 만들기
    graph = defaultdict(list)
    
    for i in tickets:
        graph[i[0]].append(i[1])
    

    #알파벳순으로 빠른 값으로 출력하기 위해 자식노드들 정렬
    for j in graph.keys():
        graph[j].sort(reverse=True)

    answer = dfs("ICN",graph)

    #거꾸로 경로를 구했기 때문에 한번 뒤집어주어야됨
    answer.reverse()

    return answer

結果