프로그래머스 여행경로 문제

접근 방식(알고리즘 분류)

• 백트래킹

내 풀이

from collections import defaultdict

def solution(tickets):
    def recur(now, graph, route):
        #global result
        if len(route) == len(tickets) + 1:
            temp = route[:]
            result.append(temp)
            return
        for i in graph[now]:
            if i[1] == False:
                route.append(i[0])
                i[1] = True
                recur(i[0], graph, route)
                i[1] = False
                route.pop()

    graph = defaultdict(list)
    result = []

    for i in tickets:
        graph[i[0]].append([i[1], False])

    recur("ICN", graph, ['ICN'])
    result.sort()

    return result[0]

풀이 설명

• defaultdict를 이용해서 graph를 비교적 쉽게 초기화했다.
• 가능한 모든경로를 백트래킹을 이용해서 구한뒤 --> 가능한 경우의 수들을 정렬했다.
• global result로 설정하니 값이 계속 바뀌었다 --> 이유는 다시 연구해볼 계획이다.
• 위의 문제의 해결방법으로 deepcopy를 이용했다. --> 습관화 해야겠다. --> [:]