Level 3. 여행경로

Level 3. 여행경로

 

 

코드는 짧지만 푸는 데는 오래 걸렸다.

 

tickets 배열을 직접 넘겨 순회하면서 갈 수 있는 목적지를 찾아도 되지만, 빠르게 찾기 위해 unordered_map에 미리 운항 정보를 담아 이용했다.

• multiset에 저장했으므로, DFS에서 가장 처음 만족하는 항공편 정보가 알파벳 순으로 가장 앞서는 경로가 된다.

 

중복된 같은 티켓이 있을 수 있다는 조건이 문제에 안 나와있었는데 이것을 고려해 풀어야 한다.

• 그래서 set 대신 multiset을 사용했다.

 

각 경로마다 항공편 정보, 정답 vector를 관리해야 하기 때문에 레퍼런스가 아닌 값으로 넘겨야 한다.

 

모든 티켓을 사용하지 못하고 여행이 끝났으면 빈 vector를, 아니면 DFS를 계속 수행한다.

 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>

using namespace std;

vector<string> rDFS(string city, vector<string> answer, unordered_map<string, multiset<string>> graph, int nUsed, int nTickets)
{
    answer.emplace_back(city);

    if (nTickets <= nUsed)
        return answer;

    for (string dest : graph[city])
    {
        unordered_map<string, multiset<string>> grp(graph);
        grp[city].erase(grp[city].find(dest));

        vector<string> result = rDFS(dest, answer, grp, nUsed + 1, nTickets);

        if (!result.empty())
            return result;
    }

    return {};
}

vector<string> solution(vector<vector<string>> tickets)
{
    vector<string> answer;
    unordered_map<string, multiset<string>> graph;

    for (vector<string>& ticket : tickets)
        graph[ticket[0]].emplace(ticket[1]);

    return rDFS("ICN", answer, graph, 0, tickets.size());
}