[ 프로그래머스 여행 경로 (Lv3) ] (C++)

프로그래머스의 여행경로(Lv3) 문제이다.

[ 문제풀이 ]

항공권이 주어질 때, 모든 도시를 방문할 때 그 경로를 알파벳순으로 정렬했을 때 가장 빠른 경로를 구해야 하는 문제이다.

본인은 완전탐색, 완전탐색 중에서도 깊이우선탐색(DFS)를 이용해서 접근하였다.

가장 먼저 매개변수로 주어지는 tickets, 즉, 항공권들을 정렬시켜 주었다.

왜냐하면, 알파벳순으로 정렬했을 때 가장 빠른 경로를 구해야 하기 때문에, 애초에 완전탐색을 진행하기에 앞서, 알파벳순으로 빠른 순서의 항공권들을 우선적으로 탐색하기 위해서이다.

탐색 도중, 모든 티켓을 다 사용해서 모든 방문지점을 다 방문했다면 더 이상의 탐색은 필요없이 그 경로를 그대로 return 시켜 주면 된다. 왜냐하면 이미 항공권들이 정렬을 해 놓은 상태이기 때문에, 이 후에 또 다른 경로가 발생하더라도, 그 경로는 기존에 나온 경로보다 알파벳 순으로 비교했을 때 더 빠를 수 없기 때문이다.

그럼 탐색을 하는 과정을 구체적으로 알아보자.

먼저, 탐색을 할 때 중요한 것은 중복된 탐색을 하면 안된다는 것인데, 처음에는 '도시를 기준으로 Visit 배열을 선언 후 관리' 하는 방법을 생각해 봤지만, 하나의 도시가 항공권에서 2개 이상 나오기 때문에 도시를 Visit배열로 관리하기에는 조금 애매한 부분이 있었다. 그래서 '티켓을 Visit배열로 관리' 해주었다.

매개변수로 주어지는 항공권을 관리해 줌으로써, "현재 A - B로 가는 항공권을 사용하려고 했는데, 기존에 사용한적이 있는지?" 를 탐색해 주었다. 기존에 사용된 항공권이라면 다른 항공권을 사용하도록 구현하였다.

또한, 탐색 중간중간에 계속 경로를 저장해 주기 위해서 Vector를 하나 선언해서 탐색을 진행해주었고, 탐색 도중 모든 티켓을 다 사용해서 모든 도시를 다 방문하였다면 그대로 탐색을 종료해 주었다.

위에서도 말했지만, 또 다른 경로가 더 존재할 수는 있지만, 우리는 이미 정렬을 해놓은 상태이기 때문에 또 다른 경로는 결코 알파벳순으로 비교했을 때 이미 나온 경로보다 더 빠를 수 없기 때문이다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool DFS(string Cur, vector<vector<string>> Ticket, vector<string> &answer, vector<bool> &Visit, int Use_Ticket)
{
    answer.push_back(Cur);
    if (Use_Ticket == Ticket.size()) return true;
    
    for(int i = 0 ; i < Ticket.size(); i++)    
    { 
        if (Ticket[i][0] == Cur && Visit[i] == false)
        {
            Visit[i] = true;
            bool T = DFS(Ticket[i][1], Ticket, answer, Visit, Use_Ticket + 1);
            if (T == true) return true;
            Visit[i] = false;
        }
    }
    answer.pop_back();
    return false;
}
 
vector<string> solution(vector<vector<string>> tickets) 
{
    vector<string> answer;
    vector<bool> Visit(tickets.size(), false);
    sort(tickets.begin(), tickets.end());
    DFS("ICN", tickets, answer, Visit, 0);
    
    return answer;
}