프로그래머스 여행경로 - 백트래킹

def dfs(ans, routes, pointNum, answer, isFinished):
    if len(ans) == pointNum:
        if not isFinished[0]:
            for i in ans:
                answer.append(i)
        isFinished[0] = True
        return
    nexts = isPossible(ans[-1], routes)
    for next in nexts:
        if not isFinished[0]:
            next[1] = True
            ans.append(next[0])
            dfs(ans, routes, pointNum, answer, isFinished)
            # 티켓 사용여부 False로 돌려놓음
            next[1] = False
            ans.pop()


def isPossible(start, routes):
    ret = []
    if start in routes :
        for i in routes[start]:
            if not i[1]:
                ret.append(i)
    return ret


def solution(tickets):
    routes = {}
    pointNum = len(tickets) + 1
    for i in tickets:
    	# 티켓 사용여부는 False
        routes[i[0]] = routes.get(i[0], []) + [[i[1], False]]
    for r in routes:
        routes[r] = sorted(routes[r], key=lambda x: x[0])
    ans = ["ICN"]

    answer = []
    dfs(ans, routes, pointNum, answer, [False])
    return answer

arr = [["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]]
print(solution(arr))

 

찾아낸 백트래킹 풀이법 규칙 적용해서 풀어봤다.

1. dfs 함수 시작시 종료조건 체크

2. 현재 시점에서 넣을 수 있는 값 후보들 찾음(isPossible함수) 반복문으로 돌며 dfs 호출

3. 다음 dfs 호출 이후에는 원상복구 해둬야함(티켓 사용여부 False로 돌려둠)