🖊️ 문제

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

---

🖊️ 풀이

처음 보자마자 아 DFS네 ! 하고 풀었다.

일단, string으로 주어진 케이스이기에, 그래프를 unordered_map으로 만들었다.
그리고, 티켓마다의 방문체크가 필요하므로, um의 value를 pair로 만들어 visited를 체크하도록 했다.
각 um의 value마다 도착지 순으로 정렬시켰다.

그 이후에, 시작지부터 DFS를 돌리는 것으로.

근데 장렬히 실패..
생각치 못한 테스트케이스가 있었다.

[["ICN", "A"], ["ICN", "B"], ["B", "ICN"]] 의 경우,
순서대로 방문하기에
ICN -> A
에서 더이상 방문하지 못하게 된다.
이 경우, 다시 A에 방문하기 전으로 되돌아가야 한다.

그래서 백트래킹 문제다 이건.

그래서, DFS한 뒤에, 방문체크를 풀어주자.

그러면 된다!
그리고, 주어진 티켓을 모두 사용했다면 리턴해주면 된다.

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

using namespace std;

bool compare(pair<bool, string>& a, pair<bool, string>& b){
    return a.second < b.second;
}

unordered_map<string, vector<pair<bool, string>>> graph;

vector<string> answer;
int total_size = 0;
int cnt = 0;
bool flag = false;

void DFS(string start) {
    answer.push_back(start);
    // cout << start << " : "  << cnt << endl;
    for (pair<bool, string>& next : graph[start]) {
        if (next.first == false) {
            cnt++;
            next.first = true;
            DFS(next.second);
            next.first = false;
            
            if (!(cnt == total_size && !flag)) {
                answer.pop_back();
                cnt--;
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    for(vector<string>& t : tickets) {
        graph[t[0]].push_back(make_pair(false, t[1]));
        total_size++;
    }
    
    for(auto& g : graph) {
        sort(g.second.begin(), g.second.end(), compare);
    }
    
    DFS("ICN");
    
    return answer;
}