旅行コース

トラベルパスの問題リンク
https://programmers.co.kr/learn/courses/30/lessons/43164
Summary
DFS/BFSで解決した問題

Description

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

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

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

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

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

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

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

［I/O例］
ticketsreturn[["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"]

Checking List

独自の問題解決
ヒントの表示と解決
答えを確認して解決

My Answer

の答えを見て問題を解決しました.

精度:

def solution(tickets):
    route = {}
    for ap in tickets:
        start, end = ap[0],ap[1]
        route[start] = sorted(route.get(start,[]) + [end], reverse=True)
        
    answer = []
    stack = ['ICN']
    while stack :
        start = stack[-1]
        if not start in route or route[start] == []:
            answer.append(stack.pop())
        else:
            stack.append(route[start].pop(-1))
    return answer[::-1]

Answer Sheet

DFS

を利用する

from collections import defaultdict
def solution(tickets):
    # 특정 티켓의 인접 리스트를 구하는 함수
    def init_graph():
        routes = defaultdict(list)
        for key, value in tickets:
            routes[key].append(value)
        return routes

    # 스택을 사용한 DFS
    def dfs():
        stack = ["ICN"]
        path = []  # 가려고하는 경로를 저장하는 변수
        while len(stack) > 0:  # stack이 비어있을 때까지
            top = stack[-1]
            # 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우
            if top not in routes or len(routes[top]) == 0:
                path.append(stack.pop())
            else:
                stack.append(routes[top].pop(0))
        return path[::-1]

    routes = init_graph()
    for r in routes:
        routes[r].sort()

    answer = dfs()
    return answer

ソース:リンク

Trial & Error

すべての空港を探索するまで経路終了を考慮せずうろうろしていた.

その結果、答えを見て初めて悟りと理解の時間が得られた.

Takeaway

このノードにアクセスしたことがあるかどうかを別途チェックしなくても,逆順序でパスを保存することを学ぶことができ,完全な探索を実現できる.

問題に応じて概念を柔軟に運用する必要がある.