[C++] 프로그래머스 : 여행경로

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;


map<string, int> m;
vector<vector<string>> v(10001);
vector<vector<bool>> BOOL(10001);
int k;
bool found = false;

void dfs(string s, vector<string>& answer){
    answer.push_back(s);
    if(answer.size() == k + 1){ // 모든 항공권을 사용한 경우
        found = true;
        return ;
    }
    int n = m[s]; // 현재 공항 인덱스
    for(int i=0;i<v[n].size();i++){
        if(!BOOL[n][i] && !found){
            BOOL[n][i] = true;
            dfs(v[n][i], answer);
            if(found) return ;
            BOOL[n][i] = false;
        }

    }
    answer.pop_back();

}

vector<string> solution(vector<vector<string>> tickets) {
    k = tickets.size();
    vector<string> answer;
    int count = 0;
    int number;
    
    // 주어진 항공권을 순회하며 공항 이름을 정수로 매핑하고, 연결 정보 저장
    for(int i=0;i<tickets.size();i++){
        if(m.find(tickets[i][0]) == m.end()){ // 출발 공항이 맵에 없는 경우
            m.insert({tickets[i][0], count});
            v[count].push_back(tickets[i][1]);
            BOOL[count].push_back(false);
            count++;
            if(m.find(tickets[i][1]) == m.end()){ // 도착 공항이 맵에 없는 경우
                m.insert({tickets[i][1], count});
                count++;
            }

        } else{ // 출발 공항이 맵에 있는 경우
            v[m[tickets[i][0]]].push_back(tickets[i][1]);
            BOOL[m[tickets[i][0]]].push_back(false);
            if(m.find(tickets[i][1]) == m.end()){ // 도착 공항이 맵에 없는 경우
                m.insert({tickets[i][1], count});
                count++;
            }
        }
    }
    
    //정렬
    for(int i=0;i<count;i++){
        sort(v[i].begin(), v[i].end());
    }
    
    dfs("ICN", answer);
    
    return answer;
}