質問リンク

問題の説明

に答える

コード#コード#

def solution(tickets):
    adj_dict, route, answer = init(tickets)
    dfs(adj_dict, route, answer, len(tickets), 'ICN')
    answer.sort()
    return answer[0]


def init(tickets):
    adj_dict = dict()
    for a, b in tickets:
        if a not in adj_dict:
            adj_dict[a] = []
        if b not in adj_dict:
            adj_dict[b] = []
        adj_dict[a].append([b, False])
    route = ['ICN']
    answer = []
    return adj_dict, route, answer


def dfs(adj_dict, route, answer, total, curr):
    if len(route) == total + 1:
        answer.append(route[:])
        return
    for i in range(len(adj_dict[curr])):
        nextt, visited = adj_dict[curr][i]
        if not visited:
            adj_dict[curr][i][1] = True
            route.append(nextt)
            dfs(adj_dict, route, answer, total, nextt)
            adj_dict[curr][i][1] = False
            route.pop()