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

여행경로

프로그래머스

 

• 내 풀이
  • 종료조건 따지려고 경로마다 num 붙여서 visited 생성
    • 근데 이전에 내 풀이 보니까 if len(path)== len(tickets)+1 해도 됐음ㅋㅋ
  • 무조건 인천에서 시작한다
  • 해당 경로 방문 유무 백트래킹

from collections import defaultdict
def solution(tickets):
    
    graph=defaultdict(list)
    num=0
    for ticket in tickets:
        s,e=ticket
        graph[s].append((e,num))
        num+=1
            
    
    def dfs(cur, path, visited):
        if False not in visited:
            result.append(path)
        
        for nxt,key in graph[cur]:
            if visited[key]==True:
                continue
                
            visited[key]=True
            dfs(nxt, path+[nxt], visited)
            visited[key]=False
    
    result=[]
    visited=[False]*(len(tickets))
    dfs("ICN", ["ICN"], visited)
    
    return sorted(result)[0]