프로그래머스: 여행경로

dfs 로 모든 경로를 다 조사하여서 사전순으로 정리한 뒤 첫 원소 반환 하면 끝

* 주의할점 : 항상 "ICN" 공항에서 출발한다.

#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include<iostream>
using namespace std;
vector<vector<string> > ans;
deque<string> q;
vector<bool> v;
vector<vector<string> > t;
void dfs(int index,int num){
    if(q.size()== t.size()+1){
       deque<string> temp;
        temp = q;
        vector<string> answer;
       while(!q.empty()){
           answer.push_back(q.front());
           q.pop_front();
       }
        q = temp;
       ans.push_back(answer);
       return ;
    }
    v[index] = true;
    for(int i=0; i<t.size(); i++){
        if(v[i]==true) continue;
        if(t[i].front() == q.back()){
            q.push_back(t[i].back());
            dfs(i,num+1);
            q.pop_back();
        }
    }
    v[index] = false;
}

bool s_sort(vector<string> a, vector<string> b){
   string ta, tb ;
    for(int i=0; i<a.size(); i++){
        ta+=a[i];

    }
    for(int i=0; i<b.size(); i++){
        tb+=b[i];
    }
    return ta<tb;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    t= tickets;
    for(int i=0; i<tickets.size(); i++){
        if(tickets[i].front() != "ICN") continue; // 항상"ICN" 공항에서 출발한다.
        v.resize(tickets.size(),false);
        deque<string> temp;
        q = temp;
        q.push_back(tickets[i].front());
        q.push_back(tickets[i].back());
        dfs(i,0);
        q.pop_back();
        q.pop_back();
    }
    sort(ans.begin(),ans.end(),s_sort);

    return ans.front();
}