🐣 문제

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43164

🐥 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
vector<string> answer;

bool dfs(vector<vector<string>> const tickets, vector<string> &route, vector<bool> &visited, string next, int n){
    route.push_back(next);

    if(route.size() == n+1){
        answer = route;
        return true;
    }
    
    for(int i = 0; i < n; i++){
        if(!visited[i] && tickets[i][0] == next){
            visited[i] = true;
            if(dfs(tickets, route, visited, tickets[i][1], n)) return true;
            visited[i] = false;   
        }
    }
    
    route.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    
    for(int i = 0; i < tickets.size(); i++){
        vector<bool> visited(tickets.size(), false);
        vector<string> route;
        
        if(tickets[i][0] == "ICN"){
            visited[i] = true;
            route.push_back("ICN");
            if(dfs(tickets, route, visited, tickets[i][1], tickets.size())){
                answer = route;
                break;
            };
        }
    }
    
    return answer;
}