프로그래머스(C++) - 여행경로

●문제

 

●입출력

 

문제해석

2차원 벡터 ticket 항공편에서 ["출발" "도착"] 항공편에서 무조건 "ICN"으로 시작해서 알파벳순으로 항공편을 RETURN

sort로 정렬한뒤 DFS로 풀이

풀이

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stdio.h>

using namespace std;

bool dfs(string current, vector<vector<string>>& tickets, vector<bool>& visited, vector<string>& answer, int use_Ticket)
{
    answer.push_back(current);
    if (use_Ticket == tickets.size())
        return true;
    for (int i = 0; i < tickets.size(); i++)
    {
        if (tickets[i][0] == current && !visited[i])
        {
            visited[i] = true;
            bool found = dfs(tickets[i][1], tickets, visited, answer, use_Ticket + 1);
            if (found)
                return true;
            visited[i] = false;
        }
    }
    answer.pop_back();
    return false;
}
vector<string> solution(vector<vector<string>> tickets) 
{
    vector<bool> visited(tickets.size(), false);
    sort(tickets.begin(), tickets.end());
    vector<string> answer;
    dfs("ICN", tickets, visited, answer, 0);
    return answer;
}
int main()
{
    vector<vector<string>>ticket = {
        {"ICN", "JFK"},
        {"HND", "IAD"},
        {"JFK", "HND"}
    };
    vector<string>answer = solution(ticket);
    for (int i = 0; i < answer.size(); i++)
    {
        printf("%s ", answer[i].c_str());
    }
    printf("\n");
    return 0;


}

 

레벨 : 3

점수 : 2