[Algorithm] 프로그래머스 - 여행경로 (C++)

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

using namespace std;

vector<string> answer;
int visit[10001];

bool dfs(string cur, vector<vector<string>> &tickets, int cnt) {
    answer.push_back(cur);

    if (cnt == tickets.size()) {
        return true;
    }

    for (int i = 0; i < tickets.size(); i++) {
        if (!visit[i] && tickets[i][0] == cur) {
            visit[i] = true;
            int success = dfs(tickets[i][1], tickets, cnt + 1);
            if (success) { //cnt == size일 경우
                return true;
            }
            //경로를 다 못도는 경우, 경로에 포함시키기 위함
            visit[i] = false;
            answer.pop_back();
        }
    }
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end()); //가능한 경로 2개 이상일 경우 알파벳 순서 앞서게
    dfs("ICN", tickets, 0);
    return answer;
}

int main() {
    vector<vector<string>> tickets = {{"ICN", "SFO"},
                                      {"ICN", "ATL"},
                                      {"SFO", "ATL"},
                                      {"ATL", "ICN"},
                                      {"ATL", "SFO"}};
    vector<string> result = solution(tickets);

    cout << "\n----" << endl;
    for (auto &i: result) {
        cout << i << " ";
    }
    return 0;
}