[프로그래머스 Lv.3] 알고리즘 고득점 Kit 깊이/너비 우선 탐색(DFS/BFS)- 여행경로

✨ 정답 ✨

function solution(tickets) {
    let answer = [];
    let visited = Array(tickets.length).fill(false);

    // 경로 정렬
    tickets.sort((a, b) => a[1].localeCompare(b[1]));

    const dfs = (current, path) => {
        path.push(current);

        // 모든 티켓 다 쓰면 경로 반환
        if (path.length === tickets.length + 1) {
            answer = path.slice();
            return true;
        }

        for (let i = 0; i < tickets.length; i++) {
            // 사용하지 않은 티켓. 현재 티켓의 도착지와 다음 티켓의 출발지가 일치할 때
            if (!visited[i] && tickets[i][0] === current) {
                visited[i] = true;
                if (dfs(tickets[i][1], path)) {
                    return true;
                }
                visited[i] = false;
            }
        }

        // 경로가 없을 때 false
        path.pop();
        return false;
    };

    dfs("ICN", []);

    return answer;
}


// 틀린 답
// function solution(tickets) {
//     let route=[];
//     let queue=["ICN"];
//     let ticketsArray=tickets.slice('');
    
//     //BFS
//     while(queue.length>0){
//         let current=queue.pop();
//         route.push(current);
//         let nextArray=[];
//         for (let i=0;i<ticketsArray.length;i++){
//             if (ticketsArray[i][0]===current){
//                 nextArray.push([ticketsArray[i][1], i])
//             }
//         }
//         nextArray.sort((a,b)=> a[0].localeCompare(b[0]));
//         if (nextArray.length>0){
//             let next=nextArray.shift();
//             queue.push(next[0]);
//             ticketsArray.splice(next[1],1);
//         }
//     }
//  return route;

// }

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡