[알고리즘C++]여행경로

오늘의 문제

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

여행경로

나의 풀이

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

using namespace std;

bool check[10001] = {false, };
vector<string> answer;
bool cmp(vector<string> a , vector<string> b){
    if(a[1] < b[1]) return true;
    else return false;
}
void dfs(string search, vector<vector<string>> t, vector<string> ans){
    ans.push_back(search);
    if(ans.size() == t.size()+1){
        answer = ans;
        return;
    }
    for(int i=0;i< t.size();i++){
        if(check[i] == false && search == t[i][0]){
            check[i] = true;
            dfs(t[i][1], t, ans);
            if(ans.size() == t.size())
                return;
            check[i] = false;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end(), cmp);
    dfs("ICN", tickets, answer);
    return answer;
}

모범 답안

#include <string>
#include <vector>

using namespace std;
int visited[1000000];
string ans_string = "a";

void dfs(vector<vector<string>> &tickets, string cur, string path, int depth) {
    if (depth == tickets.size()) {
        string p = path;
        if (path < ans_string) {
            ans_string = path;
        }
        return;
    }

    for (int i = 0; i < tickets.size(); i++) {
        if (cur == tickets[i][0] && !visited[i]) {
            visited[i] = 1;
            dfs(tickets, tickets[i][1], path + tickets[i][1], depth+1);
            visited[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;
}

배울 점

• 문제가 불친절하기도했다만 생각지 못한 입력사항이 있었다. 어떤 입력이 들어올지에 대해 분석이 필요하다.