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

A공항에서 B공항으로 가는 경로에 중점을 두면 문제가 복잡해질 수 있다. 모든 티켓을 사용하는 것이 문제이기 때문에 ICN->SFO 같은 경로는 '이 티켓을 사용할 수 있는지'를 나타내는 조건이라고 생각하고 해결해 나가는 것이 쉽다.

백트래킹으로 문제를 해결하였다.

---

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

bool dfs(vector<vector<string>> &tickets, bool visited[], vector<string> &ans, int idx)
{
    if (idx == tickets.size())
        return true;
    
    if (idx == 0)
    {
        ans.push_back("ICN");
        
        for (int i = 0; i < tickets.size(); ++i)
        {
            if (tickets[i][0] != "ICN")
                continue;
            
            visited[i] = true;
            ans.push_back(tickets[i][1]);
            if (dfs(tickets, visited, ans, idx + 1))
                return true;
            visited[i] = false;
            ans.pop_back();
        }
    }
    else
    {
        for (int i = 0; i < tickets.size(); ++i)
        {
            if (visited[i] || tickets[i][0] != ans[idx])
                continue;

            visited[i] = true;
            ans.push_back(tickets[i][1]);
            if (dfs(tickets, visited, ans, idx + 1))
                return true;
            visited[i] = false;
            ans.pop_back();
        }
    }
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets)
{   
    sort(tickets.begin(), tickets.end());
    
    vector<string> ans;
    bool visited[tickets.size()];
    memset(visited, false, sizeof(visited));
    
    dfs(tickets, visited, ans, 0);
    
    return ans;
}

알파벳 오름차순으로 방문해야 하기 때문에 tickets를 정렬해주고 시작했다. 가능한 모든 경로를 찾고 알파벳이 앞서는 경로를 리턴할 수도 있지만 불필요한 탐색을 해야 하기 때문에 비효율적이라고 생각했다.

ans는 방문한 공항의 순서대로 저장된다. visited[]는 각 티켓을 사용했는지 상태를 체크하기 위해 사용한다. idx는 사용한 티켓의 갯수이다.

일반적인 백트래킹과 흐름은 같다. 모든 티켓에 대해 반복문을 돌며 티켓[i]가 사용가능한지를 확인해주면 된다.

1. 티켓[i](ICN->SFO)의 출발지가 현재공항(ICN)과 같다면
2. 티켓[i](ICN->SFO)의 도착지인 SFO를 ans배열에 추가하고 dfs(idx + 1) 진행
3. 사용한 티켓의 갯수(idx)가 모든 티켓의 갯수와 같다면 모든 재귀를 탈출한다.
4. 조건에 맞지 않았다면 ans와 visited[]배열에서 해당 티켓을 삭제