📍[프로그래머스][DFS][백트래킹] 여행경로

여행경로

프로그래머스

 

• 📍 백트래킹 주의사항
  • 리스트를 append, pop으로 변경하면서 재귀를 도는 경우 문제가 발생할 수 있음
    • -> 변경한 경우에는 return 하기전에 path[:] 로 복사해서 쓸 것
  • 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 값에 추가하면서 백트래킹 진행 할 것

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]