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

풀이

string을 방문한것을 어떻게 체크해 줄지 고민하다가 multimap을 써서 복잡하게 풀었다.

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

vector<string> answer;
int city_cnt;
multimap<string,string>cnnt;
vector<string>route;
map<string,string>visit;
bool chk;
void dfs(int visit_cnt,string airport, vector<string>& route){
    if(visit_cnt==city_cnt){
        if(chk)
            return;
        answer=route;
        chk=true;
        return;
    }
    if(visit_cnt>city_cnt)
        return;
    vector<string> next_airport;
    //vector로 옮기기
    auto range =cnnt.equal_range(airport);

    for (auto it = range.first; it != range.second; ++it) {
        next_airport.push_back(it->second);
    }
    //오름차순 정렬
     sort(next_airport.begin(),next_airport.end());
    
    
    for(int i=0;i<next_airport.size();i++){
        route.push_back(next_airport[i]);
        //삭제
        string keyToRemove = airport;
        string valueToRemove = next_airport[i];

        auto range = cnnt.equal_range(keyToRemove);

        for (auto it = range.first; it != range.second; ) {
            if (it->second == valueToRemove) {
                it = cnnt.erase(it); 
                break;
            } else {
                ++it;
            }
        }
        dfs(visit_cnt+1,next_airport[i],route);
        route.pop_back();
        cnnt.insert({airport,next_airport[i]});
    }
    
}

vector<string> solution(vector<vector<string>> tickets) {
    city_cnt = tickets.size();
    for(int i=0;i<city_cnt;i++){
        cnnt.insert({tickets[i][0],tickets[i][1]});
    }
    route.push_back("ICN");
    dfs(0,"ICN",route);
    return answer;
}

 

효율적이지도 않고 현장에서 이렇게 못풀것 같다.
다른 풀이를 참고해서 새롭게 푼 코드

dfs나 bfs를 풀때 다음 노드로 넘어갈 수 있는 여부를 인접리스트나 인접행렬으로 구해야할 것 같아서 map으로 했는데
(시간 초과 날까봐)
이 문제는 for문을 통해서 다음 노드로 넘어갈 수 있는지를 체크해주어도 시간초과가 안났다.

또 경로가 여러개면 알파벳순으로 해서 먼저오는 것을 반환해야하기 때문에
{a,b}의 경로 (a->b)에서 b를 기준으로 오름차순 정렬을 해주었다.

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

using namespace std;
vector<bool>visit(10000);
vector<vector<string>> tickets;
vector<string> answer;
int t_size;
bool is_get_answer;
void dfs(string cur, int depth){
    
    if(is_get_answer)
            return;
    if(t_size == depth){
        
        is_get_answer=true;
    }
    for(int i=0;i<t_size;i++){
        if(!visit[i] && tickets[i][0]==cur){
            answer.push_back(tickets[i][1]);
            visit[i]=true;
            dfs(tickets[i][1],depth+1);
            if(!is_get_answer)
            {    answer.pop_back();
                visit[i]=false;
            }
        }
    }
}
bool cmp(vector<string> a, vector<string> b){
   return a[1]<b[1];
}

vector<string> solution(vector<vector<string>> _tickets) {
    tickets = _tickets;
    t_size = tickets.size();
    sort(tickets.begin(),tickets.end(),cmp);
    answer.push_back("ICN");
    dfs("ICN",0);
    return answer;
}