[Programmers] 여행경로 (C++)

문제

주어진 항공권을 모두 이용해서 여행경로 짜기

항상 ICN공항에서 출발

가능한 경우가 여러가지 있다면 알바벳 순의 경로를 리턴

생각할 것

ICN에서 출발

주어진 항공권을 모두 사용하기 위해 백트래킹 사용하기

코드

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

using namespace std;

vector<bool> visited;
vector<vector<string>> routes;
vector<string> route;

void dfs(int ticketNum, vector<vector<string>> tickets) {
    if(route.size() == tickets.size()) {
        route.push_back(tickets[ticketNum][1]); // 마지막 도착지점을 추가해주고 
        routes.push_back(route);            
        route.pop_back(); // 다시 마지막 도착지점을 지워주었다
        return;
    }

    for(int i=0; i<tickets.size(); i++){
        if(visited[i]) continue;
        visited[i] = true;
        if(tickets[ticketNum][1] == tickets[i][0]){ // 도착지와 출발지가 같은 티켓찾기
            route.push_back(tickets[ticketNum][1]);
            dfs(i, tickets);
            route.pop_back();
        }
        visited[i] = false;
    }
    
    return;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end()); // 알파벳 순을 위해 정렬
		
    for(int i=0; i<tickets.size(); i++){
        if(tickets[i][0] == "ICN") {
            // 초기화
            visited.assign(tickets.size(), false);
            vector<string>().swap(route);
            
            // 시작 지점 설정
            route.push_back(tickets[i][0]);
            visited[i] = true;
            dfs(i, tickets);
        }
    }

    return routes[0];
}

위 코드는 routes에 모든 가능한 경로를 다 담은 코드이다.

하지만 실행 속도를 더 빠르게 하고 싶다면 알파벳 순서로 정렬 후 실행되었으므로 첫번째 경우만 확인해도 된다!

그래서 결괏값도 routes[0]을 리턴해주었다.