[릿코드 / js] 332. Reconstruct Itinerary

var findItinerary = function(tickets) {
    //1.출발점이 JFK인 친구 뽑아냄.
    //2.도착점 알파벳순으로 정렬하여 제일 처음인 친구로 감.
    //3. 재귀와 while을 섞어야할듯...?
    let output = [];
    tickets.sort();
    return recurr(tickets, "JFK", output);
};

let check = function(tickets, departure)
{
    if (tickets.length === 0) return true;
    for (let i = 0; i < tickets.length; i++)
    {
        if (tickets[i][0] === departure)
        {
            return (check([...tickets.slice(0,i),...tickets.slice(i+1)], tickets[i][1]))
        }
    }
    return false;

}

let recurr = function(tickets, departure, output)
{
    output.push(departure)
    if (tickets.length === 0) return output;
    tickets.sort();
    for (let i = 0; i < tickets.length; i++)
    {
         if (tickets[i][0] === departure )
        {
            if (check([...tickets.slice(0,i),...tickets.slice(i+1)], tickets[i][1]))
            {
             return recurr([...tickets.slice(0,i),...tickets.slice(i+1)], tickets[i][1], output)
            }
        }
     }
     return output
}

-> 백트래킹이 어려워서 백트래킹을 무려 두번하는... 대 참사가 발생함

var findItinerary = function(tickets) {
    let output = [];
    tickets.sort();
    return recurr(tickets, "JFK", output, 0);
};

let recurr = function(tickets, departure, output)
{
    output.push(departure);
    if (tickets.length === 0) return output;
    for (let i = 0; i < tickets.length; i++)
    {
         if (tickets[i][0] === departure )
        {
             if (recurr([...tickets.slice(0,i),...tickets.slice(i+1)], tickets[i][1], output))
             {
                 return output;
             }
        }
     }
     output.pop();
     return false
}

--> 수정버전

 

처음에 output을 push하되, recur조건에 충족하지 않으면 pop을해서 취소해줌.