[Programmers] 43164번 여행경로.cpp

[프로그래머스] 43164번 여행경로 문제 링크

반드시 ICN에서 시작해야 한다는 조건이 있으므로, ICN에서부터 dfs를 돌리도록 하였다. 이동 가능한 경로가 2개 이상이면 사전상 빠른 경로가 출력되어야 하므로 경유지에서 이동 가능한 경로를 미리 벡터로 저장하고 오름차순으로 정렬하여 사전 순으로 다음 경로를 설정했다.

모든 티켓을 사용한 경로를 발견하였다면 앞선 조건들로 인해 사전상 가장 빠른 경로를 찾은 것이므로 별다른 조치를 하지 않고 즉시 dfs를 종료 및 결과를 출력하도록 하였다.

이를 적용한 코드 전문은 아래와 같다.

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

using namespace std;

vector<string> cityList;

bool dfs(string source, vector<vector<string>> tickets, vector<bool> use){
    vector<pair<string, int>> destList;
    
    // All ticket use test
    int useCnt = 0;
    for(auto ticket : use){
        if(ticket){
            useCnt++;
        }
    }
    if(useCnt == tickets.size()){
        return true;
    }
    
    // make destination list
    for(int index = 0; index < tickets.size(); index++){
        if((tickets[index][0] == source) && !use[index]){
            destList.push_back({tickets[index][1], index});
        }
    }
    sort(destList.begin(), destList.end());
    
    // test all destination
    for(auto dest : destList){
        if(use[dest.second]){
            continue;
        }
        use[dest.second] = true;
        cityList.push_back(dest.first);
        if(dfs(dest.first, tickets, use)){
            return true;
        }
        else{
            use[dest.second] = false;
            cityList.pop_back();
        }
    }
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<bool> use(tickets.size(), false);
    
    cityList.push_back("ICN");
    dfs("ICN", tickets, use);
    return cityList;
}