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

最初はdfsで解いたが,結果は間違っていた.

def dfs(search):
    global answer

    if len(graph[search]) == 0:
        return

    new_search = graph[search].pop()
    answer.append(new_search)
    dfs(new_search)


def solution(tickets):
    global graph
    global answer
    answer = []
    graph = defaultdict(lambda: [])

    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])

    # 알파벳 순서로 접근을 하기 위해
    for k, v in graph.items():
        v.sort(reverse=True)

    answer.append("ICN")
    dfs("ICN")
    
    return answer

最終的に解説を見て違いを見つけることにした.
https://copy-driven-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-ProgrammersPython-%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C

from collections import defaultdict

def solution(tickets):
    answer = []
    graph = defaultdict(lambda : [])

    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])

    #알파벳 순서로 접근을 하기 위해
    for k,v in graph.items():
        v.sort(reverse = True)

    stack = ["ICN"]

    #모든 행선지를 다 거쳐야 함
    while len(stack) != 0:
        search = stack[-1]

        #만약 더 이상 갈 곳이 없다면 정답 리스트에 저장
        if len(graph[search]) == 0:
            answer.append(stack.pop())
        else:
            #갈 경로가 있으면 알파벳이 낮은 순서대로 방문
            stack.append(graph[search].pop())
    answer.reverse()        
    return answer

私には間違った反例がある.
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "SFO"]]
次の条件がある場合:
dfsで解決しようとすると、［ICN］、［ATL］、［SFO］、［ATL］、［SFO］、［ATL］、［SFO］
結果が出た.
スタックコード(正しい)を使用すると、[ICN]、[SFO]、[ATL]、[SFO]、[ATL]となります.
問題条件下で,可能な経路が2つ離散している場合,アルファベット順にリードする経路を返す必要がある条件下でdfsの形で実現されるのは誤りのようだ...(もちろん、違いがあるかもしれません)
明確に結論を出すことはできないが、解決の過程で2つ程度の結論を出すことができる.
1、defaultdictの使用
2、簡単な文字列検索はstackで簡略化する