프로그래머스 Level3 - 여행경로 C++

중간에 그래프가 끊기는 경우를 생각하지 못했다.

 

알파벳이 우선순위가 되니까 먼저 정렬을 해준다.

주어진 항공권은 모두 사용해야하므로, 몇개의 항공권을 사용했는지 체크하는 cnt와

사용한 항공권은 다시 사용하지 않게 visit배열을 사용하면서 탐색한다.

 

방문하지 않았고, cur과 tickets의 출발지(tickets[i][0])가 같으면 방문표시를 하고,

dfs로 그래프가 끊기지 않는지 check변수로 체크한다.

check변수가 true이면 끊기지 않는다는 것이므로 return

아니면 visit배열을 다시 false로만들고, answer에 넣었던 것들을 다시 pop해준다.

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool dfs(string cur, vector<vector<string>>& tickets, 
         vector<int>& visit,vector<string>& answer, int cnt){
    answer.push_back(cur);
    if(cnt==tickets.size())
        return true;
    
    for(int i=0;i<tickets.size();i++){
        if(visit[i]==false && cur==tickets[i][0]){
            visit[i]=true;
            bool check=dfs(tickets[i][1],tickets,visit,answer,cnt+1);
            if(check) return true;
            visit[i]=false;
        }
    }
    answer.pop_back();
    return false;    
}
 
 
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<int> visit(tickets.size(),false);
    sort(tickets.begin(),tickets.end());
    
    dfs("ICN", tickets, visit, answer, 0);
    
    return answer;
}