[Javascript/PGS] Lv.3 : 여행경로

 

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=javascript

프로그래머스

---

프로그래머스 레벨3

DFS 유형 문제이고, 예전에 CPP로 풀었는데 js로 다시 풀어보았다.

 

한 경로로 끝까지 탐색해야하므로 깊이우선 탐색을 진행,

만약 끝까지 진행하지 못한다면 백트래킹이 필요하다!

(pop & visited false 처리)

 

 

나의 풀이

let answer = [];
let isAnswer = false;
let visited = new Array(10001).fill(false);
let Tickets;

const dfs=(now, count)=>{
    answer.push(now);
    if(count===Tickets.length) isAnswer=true;
    for(let i=0; i<Tickets.length; ++i){
        if(visited[i]) continue;
        if(now == Tickets[i][0]){
            visited[i] = true;
            dfs(Tickets[i][1], count+1);
            if(!isAnswer){
                answer.pop();
                visited[i] = false;
            }
        }
    }
}

function solution(tickets) {
    Tickets = tickets.sort();
    dfs("ICN", 0);
    return answer;
}