[Programmers] 여행경로(Lv.3)(C++)

풀이 소요시간 : 40분

반례를 떠올리지 못해서 시간이 좀 더걸렸다. Map 을 이용하여 각 공항마다 대응되는 공항의 Vector 를 만들어주고, 이를 활용하여 백트래킹을 해주면 된다.

생각 못한 반례

ICN, A ICN, B B, A 라는 3개의 항공권이 있는 상황에서 역순으로 정렬한다면

ICN -> A, B B -> A 의 상태가 되는데, 이때 A 에서 순회할 수 있는 방법이 없기 때문에 이 단계에서 탐색이 멈춰버리는 것이다. 다만 이 경우에도 Size 의 설정을 잘 해주었다면 통과 됬을 문제지만, 변수를 제대로 파악 못한 내 실수다.

전체 코드

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

map<string, vector<int>> Visit;
map<string, vector<string>> Map;

vector<vector<string>> Ans;
vector<string> Temp;

int Size;


void Dfs(string From, int Count) {
    
    if(Count == Size)
    {
        Ans.push_back(Temp);
        return;
    }
    
    for(int i = 0; i < Map[From].size(); i++)
    {
        string To = Map[From][i];
        
        if(Visit[From][i] == 1) continue;
        
        Visit[From][i] = 1;
        Temp.push_back(To);
       
        Dfs(To, Count + 1);
        
        Visit[From][i] = 0;
        Temp.pop_back();
    }
    
}

vector<string> solution(vector<vector<string>> tickets) {
    
    Size = tickets.size();
    for(int i = 0; i < Size; i++)
    {
        Map[tickets[i][0]].push_back(tickets[i][1]);
        Visit[tickets[i][0]].push_back(0);
    }
    
    for(auto& E : Map)
    {
        sort(E.second.begin(), E.second.end());
    }
    
    Temp.push_back("ICN");
    Dfs("ICN", 0);
    return Ans[0];
}