풀이전략

• 그림을 그려보면 백트래킹으로 접근하면 됨을 확실할 수 있다.
• 인덱스 번호를 어떤 방식으로 할까? 에 대한 고민이 있다.
  맨 처음에는 a -> b map 형식으로 할까? 했지만,
  문제에서 2차원 벡터로 인덱스가 주어지므로 이것을 이용하면 된다!

소스 코드

#include <string>
#include <vector>

using namespace std;

vector<bool>check;

string result = "ZZZZZ";

void backTracking(vector<vector<string>>&ticket, int idx, string word, string target)
{
    if(idx == ticket.size())
    {
        if(result > word)
            result = word;
        
        return;
    }
    
    
    for(int i = 0; i < ticket.size(); i++)
    {
        if(!check[i] && target == ticket[i][0])
        {
            check[i] = true;
            backTracking(ticket, idx + 1, word + ticket[i][1] , ticket[i][1]);
            check[i] = false;
        }
        
    }
    
    
}


vector<string> solution(vector<vector<string>> tickets) {
    
    check.resize(tickets.size());
    
    backTracking(tickets,0 ,"ICN", "ICN");
    
    
    vector<string> answer;
    
    
    
    //나누자.
    for(int i = 0 ; i < result.length(); i += 3)
    {
        string tmp = result.substr(i , 3);
        answer.push_back(tmp);
    }
    
    
    return answer;
}