[JavaScript] 프로그래머스 여행경로 LEVEL3

문제풀이

let visit;
let answer;

const dfs = (tickets, start, res, cnt) => {
    res.push(start);
    
    if (cnt === tickets.length) {
        answer = res;
        return true;
    }
    
    for (let i=0; i<tickets.length; i++) {
        if (visit[i] === 0 && tickets[i][0] === start) {
            visit[i] = 1;
            
            const result = dfs(tickets, tickets[i][1], res, cnt + 1);
            
            if (result) return true;
            
            visit[i] = 0;
            res.pop();
        }
    }
    return false;
}

function solution(tickets) {
    const arr = [...tickets].sort();
    visit = new Array(tickets.length).fill(0);
    
    dfs(arr, 'ICN', [], 0);
    
    return answer;
}

풀이

• 재귀로 DFS를 풀어야 한다.
• 재귀로 안풀면 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ICN"]] 테케를 돌렸을때 ICN -> ATL을 방문하면 다른 공항은 방문하지 못하게 된다.