[Python] 백트래킹 주의사항

📍 백트래킹 주의사항

1. 리스트를 append, pop으로 변경하면서 재귀를 도는 경우 문제가 발생할 수 있음
   • -> 변경한 경우에는 return 하기전에 path[:] 로 복사해서 쓸 것
2. append, pop 대신 재귀로 넘기는 파라미터값에서 추가해주면 복사 안해도됨

def solution(tickets):
    def dfs(start, path):
        if len(path) == len(tickets) + 1:
            answer.append(path[:])  # 리스트를 복사해서 저장
            return
        
        for i, next in enumerate(dict[start]):
            dict[start].pop(i)  # 항공권 사용
            path.append(next)
            dfs(next, path)
            path.pop()  # 경로 복구
            dict[start].insert(i, next)  # 항공권 복구

def solution(tickets):
    def dfs(start, path):
        if len(path) == len(tickets) + 1:
            answer.append(path)
            return
        
        for i, next in enumerate(dict[start]):
            dict[start].pop(i)
            dfs(next, path+[next]) #재귀보낼 때 값 변경
            dict[start].insert(i, next)

 

• dict[start]에서 제거할 때 idx 없이 제거하고 추가하면 값이 변경될 수 있음
  • -> 정확한 idx  값을 제거하고 보내고, 
  • 다시 해당 idx 값에 추가하면서 백트래킹 진행 할 것

        for i, next in enumerate(dict[start]):
            dict[start].pop(i)
            dfs(next, path+[next])
            dict[start].insert(i, next)

 

• 참고) 프로그래머스 여행경로 풀이

https://yygs321.tistory.com/544

from collections import defaultdict

def solution(tickets):
    def dfs(start, path):
        if len(path) == len(tickets) + 1:
            answer.append(path)
            return
        
        for i, next in enumerate(dict[start]):
            dict[start].pop(i)
            dfs(next, path+[next])
            dict[start].insert(i, next)
            
    answer = []
    
    dict=defaultdict(list)
    for s,e in tickets:
        if dict[s]:
            dict[s].append(e)
            continue
            
        dict[s]=[e]
        
    dfs('ICN', ['ICN'])
    
    answer.sort()
        
    return answer[0]