[프로그래머스] 여행경로 (Lv3)

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

코딩테스트 연습 - 여행경로

C++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> answer;
vector<int> visit(10001);
vector<string> temp;

bool DFS (string from, int cnt, vector<vector<string>> tickets) {
    temp.push_back(from);
    if(cnt==tickets.size()){
        answer=temp;
        return true;
    }
    for(int i=0;i<tickets.size();i++){
        if(tickets[i][0]==from && visit[i]==0){
            visit[i]=1;
            bool suc = DFS(tickets[i][1],cnt+1,tickets); //성공하면 끝내야함(알파벳 빠른 순을 찾는 것이기 때문)
            if(suc==true) return true;
            visit[i]=0;
        }
    }
    temp.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    
    sort(tickets.begin(),tickets.end());
    DFS("ICN", 0, tickets);
    return answer;
}

JS

let answer = [];
let temp=[];
let visited=Array.from({length: 10001}, () => 0);

function DFS(from,tickets,cnt) {
    temp.push(from);
    if(cnt===tickets.length){
        answer=temp;
        return true;
    }
    for(let i=0;i<tickets.length;i++) {
        if(from===tickets[i][0] && visited[i]==0) {
            visited[i]=1;
            let suc = DFS(tickets[i][1],tickets,cnt+1);
            if(suc===true) return true;
            visited[i]=0;
        }
    }
    temp.pop();
    return false;
}

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