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

프로그래머스

 

• 완전 탐색 문제
• 단, 경로가 2개 이상일 때 알파벳 순서가 앞서는 경로를 리턴하라 했으므로 정렬하여 알파벳 순서대로 탐색할 수 있도록 하였음

 

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

using namespace std;

// 무조건 ICN 공항에서 출발
// 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 리턴
// 일단 정렬하면 알파벳 순서로 탐색할 수 있을듯
// 완전 탐색 문제. DFS로 접근

bool dfs(string cur, vector<vector<string>> tickets, vector<string> &answer, vector<bool> &Used, int cnt) {
    // 방문한 공항 저장
    answer.push_back(cur);
    
    // 모든 티켓 사용 완료
    if(tickets.size() == cnt) return true;
    
    // 티켓 배열을 순회하며
    for(int i = 0; i < tickets.size(); i++) {
        // 출발지가 현재 공항이고 사용한적 없는 티켓이라면
        if(tickets[i][0] == cur && !Used[i]) {
            // 사용으로 바꾸고
            Used[i] = true;
            
            // 더 안쪽으로 탐색
            if(dfs(tickets[i][1], tickets, answer, Used, cnt + 1)) return true;
            
            // 위 if 문이 거짓이 되면 모든 항공권 사용 실패이므로 백트래킹
            Used[i] = false;
        }
    }
    
    // 마찬가지로 백트래킹
    answer.pop_back();
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> Used(tickets.size(), false);
    
    // 정렬
    sort(tickets.begin(), tickets.end());
    
    // dfs
    dfs("ICN", tickets, answer, Used, 0);
    
    return answer;
}