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

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

문제 링크

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int visited[1001];
void solve(vector <vector<string>>& candidates, vector<string>& temp, vector<vector<string>>& tickets, string target){
    
    if(temp.size() == tickets.size() + 1){
        candidates.push_back(temp);
        return;
    }

    //갈 수 있는 한 깊은 곳 까지 가자
    for(int i=0; i<tickets.size(); i++){
        if(!visited[i] && target == tickets[i][0]){
            temp.push_back(tickets[i][1]);
            visited[i] = 1;
            solve(candidates, temp, tickets, tickets[i][1]);
            visited[i] = 0;
            temp.pop_back();
        }
    }
    
}
vector<string> solution(vector<vector<string>> tickets) {
    vector <vector<string>> candidates;
    vector <string> temp;
    for(int i=0; i<tickets.size(); i++){
        if(tickets[i][0] == "ICN"){
            temp.push_back("ICN"); // 시작점 저장
            temp.push_back(tickets[i][1]);
            visited[i] = 1;
            solve(candidates, temp, tickets, tickets[i][1]);
            visited[i] = 0;
        }
        temp.clear();
    }

    sort(candidates.begin(), candidates.end());

    return candidates[0];
}

• 전형적인 백트래킹, dfs 문제이다.
• 문제 해설이 좀 부족한데, https://programmers.co.kr/learn/questions/7894 이 링크에서 도움을 많이 받았다.
• dfs 탐색으로 갈 수 있는 모든 경로를 저장하고, 티켓의 갯수 + 1개가 되면 후보 벡터에 저장한다.
• 모든 탐색이 끝난 후, 후보 벡터를 sort로 알파벳 순서대로 정렬 후, 제일 앞쪽의 벡터를 리턴한다.