[프로그래머스]여행경로

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int tiketsLen;
int count = 0;
bool check[10001];
string airport[10001];
vector<vector<string>> store;
vector<vector<string>> allTickets;
 
void DFS(string curPort, int count) {
    if(count == tiketsLen) {
        vector<string> temp(count + 1);
        for(int idx = 0; idx < count + 1; idx++) {
            temp[idx] = airport[idx];
        }
        store.push_back(temp);
        return;
    }
    
    for(int idx = 0; idx < allTickets.size(); idx++) {
        if(allTickets[idx][0] != curPort) { continue; }
        if(check[idx]) { continue; }
        check[idx] = true;
        airport[count + 1] = allTickets[idx][1];
        DFS(allTickets[idx][1], count + 1);
        check[idx] = false;
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    
    allTickets.clear();
    allTickets.assign(tickets.begin(), tickets.end());
    fill(check, check + 10001, false);
    
    tiketsLen = tickets.size();
    
    airport[0] = "ICN";
    DFS(airport[0], 0);
    
    sort(store.begin(), store.end());
    
    for(int idx = 0; idx < store[0].size(); idx++) {
        answer.push_back(store[0][idx]);
    }
     
    return answer;
}