🔎 여행경로

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/43164

📄 제출 코드

let answer = [];
function solution(tickets) {
    tickets.sort();
    let len = tickets.length;
    let visited = new Array(len).fill(false);
    
    dfs(tickets, "ICN", len, 0, visited)
    return answer[0];
}

function dfs(tickets, start, len, depth, v, arr = []) {
    arr.push(start);
    if (depth == len) {
        answer.push([...arr]);
    } 
    for (var i = 0; i < len; i++) {
        if (!v[i] && tickets[i][0] == start) {
            v[i] = true;
                
                dfs(tickets, tickets[i][1], len, depth + 1, v, arr);
                v[i] = false;
            }
        }
    
    arr.pop();
}

let tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	;
console.log(solution(tickets));

dfs로 찾아찾아가면 나올거 같았는데 나와서 맞췄다.
문제에서 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다라고 되있습니다. 그래서 sort()로 정렬을 해줍니다.
sort를 먼저 해도 되는 이유는 문제에서 시작점이 무조건 ICN부터라고 명시 되있기 때문입니다. (처음에 문제 제대로 안 읽고 tickets[0][0]했다가 틀림,,)
그리고 방문체크할 visited배열에 false로 채워줍니다.

dfs함수에서는 tickets배열, 시작점(ICN), tickets길이, 깊이(0), visited, 빈배열로 시작합니다.
depth가 tickets배열 길이만큼되면 answer에 저장해둔 arr를 push하고, 하나씩 꺼냅니다.

dfs를 도는 조건은 방문하지 않았고, 출발지(tickets[i][0])가 start면 도착지인 tickets[i][1]를 출발지로 다음 목적지를 찾습니다.