C++:: 프로그래머스 < 여행경로 >

dfs를 사용하여 모든 티켓을 사용하는 경우 중 사전순으로 가장 빠른 것을 반환해주면 되는 문제이다. 주의해야 할 점은 중복되는 경로의 티켓이 들어올 수도 있고 이에 대한 방문처리를 잘 해주어야 한다는 점이다.
예시로 A -> B 티켓이 여러장 일 수 있고 이에 대한 방문 처리는 독립적이어야 한다는 의미이다.

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

unordered_map<string, vector<pair<string, bool>>> um;
int n;
bool isDone = false;

void dfs(int cnt, vector<string>& answer) {
    if (cnt == n) {// 티켓 다 썻으면
        isDone = true;// 종료 플래그
        return;
    }
    string from = answer[cnt-1];
    for (auto& to : um[from]) {
        if (isDone) return ;
        if (to.second) continue;
        string ticket = from + to.first;
        answer[cnt] = to.first;
        to.second = true;
        dfs(cnt+1, answer);
        to.second = false;
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    n = tickets.size() + 1;
    vector<string> answer(n, "ICN");// 인천공항 시작
    for (int i=0; i<tickets.size(); i++) {
        um[tickets[i][0]].push_back({tickets[i][1], false});// 도착지 배열에 방문 여부도 같이 생각해서 넣는다.
    }
    for (auto& u : um) {// 사전순이기 때문에 정렬
        sort(u.second.begin(), u.second.end());
    }
    dfs(1, answer);
    return answer;
}