[ 프로그래머스 ] 여행경로

문제

---

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

풀이

---

#pragma once

#include <iostream>
#include <string>
#include <vector>
#include <string>
#include <stack>
#include <cmath>
#include <algorithm> 
#include <map>
#include <set>

using namespace std;

vector<string> answer;

bool DFS(map<string, multiset<string>>&tickets_map, string start, int count, int max)
{
    if (count == max)
        return true;

    for (auto iter = tickets_map[start].begin(); iter != tickets_map[start].end();)
    {
        answer.push_back(*iter);
        string backup = *iter;
        iter = tickets_map[start].erase(iter);
        bool check = DFS(tickets_map, backup, count + 1, max);
        if (!check)
        {
            tickets_map[start].insert(backup);
            answer.pop_back();
        }
        else
            return true;
    }

    return false;
}



vector<string> solution(vector<vector<string>> tickets)
{
    //모든 항공권을 사용해야하고, 모든 도시 방문할 수 없는 경우는 X
    map<string, multiset<string>> mm;

    //경로가 2개 이상 존재할 경우, 알파벳순서가 앞서는 경우를 선택
    //멀티셋은 자동으로 sort해주니까 따로 sort 필요 X
    for (int i = 0; i < tickets.size(); i++)
    {
        mm[tickets[i][0]].insert({ tickets[i][1] });
    }
    
    //시작 위치 ICN
    string startingPoint = "ICN";
    answer.push_back(startingPoint);

    for (int i = 0; i < mm[startingPoint].size(); i++)
    {
        DFS(mm, startingPoint,0, tickets.size());
    }





    return answer;
}