[Python][DFS] 여행경로

프로그래머스

여행경로

 

프로그래머스

 

candidates = []
def visit(start, graph, visited, cnt, route):
    global candidates
    if cnt == len(graph):
        candidates.append(route.split(" "))
    else:
        for i in range(len(graph)):
            if visited[i] == 0 and graph[i][0] == start:
                go = []
                for j in range(len(visited)):
                    go.append(visited[j])
                go[i] = 1
                visit(graph[i][1], graph, go, cnt+1, route+" "+graph[i][1])

def solution(tickets):
    answer = []
    tickets.sort()
    visited = [0] * len(tickets)
    visit("ICN", tickets, visited, 0, "ICN")
    return candidates[0]

 

def dfs(graph, n, path, here):
    path.append(here)

    if len(path) == n+1:
        return True

    if here not in graph:
        path.pop()
        return False

    for i in range(len(graph[here])):
        there = graph[here][-1]
        graph[here].pop()

        if dfs(graph, n, path, there):
            return True

        graph[here].insert(0, there)

    path.pop()
    return False

def solution(tickets):
    routes = dict()

    for (start, end) in tickets:
        routes[start] = routes.get(start, []) + [end]

    for r in routes.keys():
        routes[r].sort(reverse=True)

    n = len(tickets)
    path = []

    if dfs(routes, n, path, "ICN"):
        answer = path

    return answer