[프로그래머스] 여행경로 JS

접근방법💡

모든 티켓들의 출발지를 키값으로 하는 인접리스트를 만들기
알파벳 순으로 정렬
dfs로 탐색
탈출 조건은 경로의 길이가 tickets의 length와 같을 때

function solution(tickets) {
   
    const adjacencyList = {};
    
    let result=[];
    
    //인접리스트 [key=출발지]:도착지[] 
    tickets.forEach(t=>{
        const [dep, arr]=t;
        const tmp=adjacencyList[dep]||[];
        tmp.push(arr);        
        adjacencyList[dep]=tmp;
    });
    
    //알파벳 순으로 정렬
    for(key in adjacencyList){
        adjacencyList[key].sort();
    }
    

    
    //재귀함수 dfs
    //path=지금까지의 경로, dep=출발지
    //백트래킹을 해야 하기 때문에 인수로 지금까지 경로를 담은 배열을 전달해줌
    function dfs(path, dep){
    
    //탈출 조건 = 경로의 길이가 total가 같을 때
        if(path.length===tickets.length){
        	//result 배열에 마지막으로 받은 dep값 넣어주기
            result = [...path, dep];
            return true;
        }
        
        const temp=adjacencyList[dep]?[...adjacencyList[dep]]:[];

        temp?.forEach(city=>{
        	//리스트를 큐라고 생각하고 맨 앞의 도시를 pop하고
            //다시 dfs로 탐색
            adjacencyList[dep].shift();
            if(dfs([...path, dep], city)){
                return true;
            };
           //조건에 맞는 경로를 찾기 못했을 경우
           //제거했던 도시를 뒤에 다시 넣어줌
            adjacencyList[dep].push(city);
        })
        
        return false;
        
        
    }
    dfs([],"ICN");
    
  return result;
    
    


}

https://school.programmers.co.kr/learn/courses/30/lessons/4316