여행경로

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

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

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

bool find(vector<bool>&check,vector<vector<string>> &tickets, int idx, vector<string>&route){
    
    string goal = tickets[idx][1];
    route.push_back(goal);
    if(route.size()==tickets.size()+1){return true;}

    for(int i=0; i<tickets.size(); i++){
        if((tickets[i][0]==goal)&&(check[i]==false)){
            check[i]=true;
            if(find(check,tickets,i,route)){return true;};
            check[i]=false;
        }
    }
    route.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    
    vector<string> answer;
    vector<string> route;
    
    sort(tickets.begin(),tickets.end());
    for(int i=0; i<tickets.size(); i++){
        vector<bool>check(tickets.size(),false);
        if(tickets[i][0]=="ICN"){
            check[i]=true;
            route.push_back("ICN");
           if(find(check,tickets,i,route)==true)break;
            route.clear();
        }
    }
    answer = route;
    return answer;
}