프로그래머스. 여행경로(c++) / DFS + 백트래킹

[핵심 요소]

계속 테케, 4번이 틀려서 봤더니....

왠걸 같은 항공편이 2번 있어도 괜찮기 때문에 from->to로 가는 항공편을 한 번 갔다고 해서 

못가게 하면 안되는 것이었다.....즉, ["ICN", "A"], ["ICN", "A] 똑같은 항공편이 2개 있을 수도 있다는 것!

그래서 visited[][] 2차 배열을 사용해서 visited[from][to]의 항공편 개수를 저장해주었고

방문할때마다 -1씩 차감했다.

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
map<string, vector<string>> m;
vector<string> ans;
int kind = 0;
bool check = false;
int visited[10001][10001] = {0, };
map<string, int> idx;
vector<string> Ans;
 
void dfs(string airport){
    if(check==true) return;
    if(kind==ans.size()){
        for(int i=0; i<ans.size(); i++){
            Ans.push_back(ans[i]);
        }
        check = true;
        return;
    }
    
    sort(m[airport].begin(), m[airport].end());
    for(int i=0; i<m[airport].size(); i++){
        if(visited[idx[airport]][idx[m[airport][i]]]==0) continue;
        visited[idx[airport]][idx[m[airport][i]]]--;
        ans.push_back(m[airport][i]);
        dfs(m[airport][i]);
        ans.pop_back();
        visited[idx[airport]][idx[m[airport][i]]]++;
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    kind = tickets.size()+1;
    
    int Idx = 0;
    for(int i=0; i<tickets.size(); i++){
        string from = tickets[i][0];
        string to = tickets[i][1];
        if(idx.count(from)==0){
            idx[from] = Idx++;
        }
        if(idx.count(to)==0){
            idx[to] = Idx++;
        }
        visited[idx[from]][idx[to]]++;
        m[from].push_back(to);
    }
    
    ans.push_back("ICN");
    sort(m["ICN"].begin(), m["ICN"].end());
    
    for(int i=0; i<m["ICN"].size(); i++){
        if(visited[idx["ICN"]][idx[m["ICN"][i]]]==0) continue;
        visited[idx["ICN"]][idx[m["ICN"][i]]]--;
        ans.push_back(m["ICN"][i]);
        dfs(m["ICN"][i]);
        ans.pop_back();
        visited[idx["ICN"]][idx[m["ICN"][i]]]++;
    }
    
    return Ans;
}