[Lv.3] 여행경로

출처. 프로그래머스

프로그래머스

 

기본적인 DFS 방식으로 풀면 된다.

ICN로 시작해서 모두 방문할 수 있는 경로를 저장한다.

그 이후에 알파벳 순서가 가장 빠른것이 정답이다.

아래 코드의 주석 참고~

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

using namespace std;

bool visitable[10000];
vector<vector<string>> answerList; // 경로를 저장하는 경로 리스트
size_t totalSize = 0;

void DFS(vector<vector<string>>& ticket, vector<string>& answer) {
    if (answer.size() == totalSize+1) { // 항공권 탐색이 다 끝났다면, 경로를 경로리스트에 저장
        answerList.push_back(answer);
        return;
    }
    
    for (size_t idx = 0 ; idx < totalSize ; idx++) {
        if (answer.back() == ticket[idx][0] && visitable[idx]) { // 경로 마지막과 항공권의 시작을 비교하고 방문 가능한지 확인
            answer.push_back(ticket[idx][1]); // 경로에 항공권의 도착지를 설정
            visitable[idx] = false; // 한번 방문했으니 방문 여부를 false로 설정
            DFS(ticket, answer);
            answer.pop_back();
            visitable[idx] = true; 
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    totalSize = tickets.size();
    
    for (size_t i = 0 ; i < totalSize ; i++) {
        visitable[i] = true;
    }
    
    vector<string> answer{"ICN"}; // 시작위치는 ICN로 설정
    
    DFS(tickets, answer);
    
    sort(answerList.begin(), answerList.end()); // 경로가 담긴 List를 오름차순으로 정렬
        
    return answerList[0];
}