여행경로 - level 3

해결방법

dfs, bfs문제이고 솔직히 쉬운 문제였는데 오래걸렸다. 첫 번째는 문제에 대한 오해였다. 이 티켓을 사용해서 모든 도시를 다 방문해야만한다. 단순히 dfs를 통해서 사용하는 것이 아니라 실제 다 모든 도시 방문 && 모든 티켓 사용인지를 확인해줘야만 한다.

전체 소스

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
int T;
vector<bool> v;
vector<string> dfs(string s, vector<vector<string>> t, vector<string> ans, int cnt) {
    ans.push_back(s); 
    if (cnt == T) return ans;
    vector<string> tmp;
    for (int i = 0; i < t.size(); ++i) {
        if (t[i][0] == s && !v[i]) {
            v[i] = true;
            tmp = dfs(t[i][1], t, ans, cnt+1);
            if (tmp.size() == T+1) return tmp;
            v[i] = false;
        }
    }
    return tmp;
}
vector<string> solution(vector<vector<string>> t) {
    vector<string> ans;
    T = t.size();
    v.resize(t.size(), false);
    sort(t.begin(), t.end());
    ans = dfs("ICN", t, ans, 0);
    return ans;
}