[프로그래머스] 여행 경로, C++

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상ICN공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

tickets	return
[[ICN,JFK], [HND,IAD], [JFK,HND]]	[ICN, JFK, HND, IAD]
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]

입출력 예 설명

예제 #1

[ICN,JFK,HND,IAD] 순으로 방문할 수 있습니다.

예제 #2

[ICN,SFO,ATL,ICN,ATL,SFO] 순으로 방문할 수도 있지만 [ICN,ATL,ICN,SFO,ATL,SFO] 가 알파벳 순으로 앞섭니다.

 

풀이 

• dfs로 풀이 
• 시작점은 항상 ICN
• 가능한 경로가 두개 이상일 경우 알파벳 순서가 앞서는 경로를 return해야 하므로, 정렬 필요 

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

using namespace std; 
bool dfs(string start, vector<vector<string>>& tickets, vector<bool>& visit, vector<string>& route, vector<string>& answer, int count) { 
    route.push_back(start); //시작점 push
    if (count == tickets.size()) { //주어진 티켓을 다 쓰면 return
        answer = route; 
        return true; 
    } 
    for (int i=0 ; i<tickets.size() ; i++) { //티켓 개수만큼 반복
        if (tickets[i][0] == start && visit[i] == false) { //start에서 시작하는 티켓이고, 해당 티켓을 쓴 적이 없으면
            visit[i] = true; //해당 티켓 사용
            //해당 티켓의 도착지를 시작점으로해서 다시 dfs
            bool success = dfs(tickets[i][1], tickets, visit, route, answer, count+1); 
            if (success) //해당 티켓의 도착지를 시작점으로 해서 dfs해서 탐색에 성공하면 
                return true; //종료 
            visit[i] = false; //아니면, 해당 티켓을 사용하지 않은 것으로 변경 (탐색에 실패했으므로)
        } 
    } 
    route.pop_back(); //start를 시작으로 가능한 모든 경로를 탐색했으므로, start를 route에서 제거 
    return false; 
} 
vector<string> solution(vector<vector<string>> tickets) { 
    vector<string> answer, route; 
    vector<bool> visit(tickets.size(), false); //티켓을 사용했는지 여부를 담는 배열 
    sort(tickets.begin(), tickets.end()); //알파벳 순으로 정렬 (가능한 경우가 2개 이상일 경우 대비)
    dfs("ICN", tickets, visit, route, answer, 0); //시작점은 항상 인천공항 
    return answer; 
}