[アルゴリズム]旅行ルート

1592 ワード

テキストリンク

程序旅行路线的问题

:一度に答えられなかったのは、問題を正しく理解できなかったからです.

もんだいぶんせき

:航空券(往復の片道航空券ではありません)は航空券として発行されます.これらの航空券に基づいて「旅行ルート」を制定します.この場合、チケットはICNから出発し、飛行機、飛行機、飛行機でどこかに到着しなければなりません.つまり、途中に航空券がない、換言すれば、A->B->Cに行く場合、A->Bの航空券がない、ということになります.完璧に与えられた.そのため、片道券を元に、旅行経路を順番に並べて返すのが問題です.この場合、可能な旅行ルートが2つを超える場合は、事前の順序で空港を考えるときは、先に前の単語に対応する空港に行くべきです.

私が逃したのは少しです。

事前の順番で先に前の空港に行く条件を受け入れすぎた.本来の意味では、まずすべての航空券が使える旅行ルートを探して、もし見つけたら、2つを超えると、事前の順番で比較して選択します.しかし、私はまず辞書の順番を使います.最初は、事前の順序に逆行した旅行経路は全く探求されなかった.それで問題になった.

もんだいせっけい

問題は

DFS+遡及によって解決できる.この場合,再帰関数を呼び出すと,再帰関数を呼び出すたびに航空券が1枚使用されるので,全票を使用すると再帰関数が返され,基本条件に相当する.この場合、航空券情報を元に最初から空港名順に並べ替えられているので、すぐに終了することができます.

インプリメンテーションコード


answer=  ["ICN"]

def recursion(node,d,l):
    global answer
    
    if l == 0:
        return True
    try:
        if d[node]:
            pass
    except:
        return
    
    for idx, airport in enumerate(d[node]):
        answer.append(airport)
        top = d[node].pop(idx)
        
        if recursion(top,d,l-1):
            return True

        d[node].insert(idx,top)
        answer.pop()


    
def solution(tickets):
    d = {}
    
    for el in tickets:
        try:
            d[el[0]].append(el[1])
        except:
            d[el[0]] = [el[1]]
            
    for key, val in d.items():
        val.sort()
        d[key] = val
        
    l = len(tickets)
    root = "ICN"
    recursion(root,d,l)
    
    return answer

:問題をよく読む.私はずっと答えています.指紋が短いほど問題が友好的ではありません.深く理解しなければならない.

Reference

この問題について([アルゴリズム]旅行ルート), 我々は、より多くの情報をここで見つけました https://velog.io/@0715yk/Algorithm-여행-경로

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

[C++]BOJ 10814号:年齢順

オブジェクト