[DFS/BFS] 여행경로

문제의 핵심은

모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

이다.

예를 들어

[["ICN", "ATL"], ["ICN", "SEO"], ["SEO", "ICN"]]

와 같은 경우 알파벳 순서대로라면

ICN -> ATL 이후에 연결될 수 없으므로

ICN-SEO-ICN-ATL와 같이 연결되어야 한다.

 

DFS로 해결하기 위해서

모든 경로의 답을 담아두는 dfsArray를 만들어두고

모든 경로를 돈 경우에만 answer에 더해 마지막에 정렬을 통해 정렬된 답을 도출했다.

 

주의할 점은

splice를 통하여 타겟이 된 티켓을 배열에서 제거하였다는 점이다.

var answer = [];
 
function DFS(tickets,target,dfsArray){
    if(tickets.length == 0){
        answer.push(dfsArray)
    }
    for(var i in tickets){
        trackking(tickets, i, target, dfsArray);
    }    
}
 
function trackking(tickets, i, target, dfsArray) {
    if (tickets[i][0] == target) {
        let remainningTickets = tickets.slice();
        remainningTickets.splice(i, 1);
        let tempDfsArray = dfsArray.slice();
        tempDfsArray.push(tickets[i][1]);
        DFS(remainningTickets, tickets[i][1], tempDfsArray);
    }
}
 
function solution(tickets) {    
    DFS(tickets,'ICN',["ICN"]);
    return answer.sort()[0];
}