[프로그래머스]여행경로

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

코딩테스트 연습 - 여행경로 | 프로그래머스

MST인줄 알았는데 그냥 DFS로 전체 돌아주고 사이즈가 되었을 때, 최대값을 갱신하는 경우로 하면 됨!!

 

#include <string>
#include <vector>
 
using namespace std;
 
bool isV[10001];
string ans_string="a";
 
void dfs(vector<vector<string>> &tickets,string cur,string path,int len){
    if(len==tickets.size()){
        if(path < ans_string) ans_string = path;
        return;
    }
    
    for(int i=0;i<tickets.size();i++){
        if(!isV[i] && tickets[i][0]==cur){
            isV[i]=1;
            dfs(tickets,tickets[i][1],path + tickets[i][1],len+1);
            isV[i]=0;
        }
    }
}
 
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    dfs(tickets,"ICN","ICN",0);
    for(int i=0;i<ans_string.size();i+=3){
        answer.push_back(ans_string.substr(i,3));
    }
    return answer;
}