여행경로 43164

문제

접근 방법

백트래킹을 사용해 주는 것이 옳다고 생각했다. 왜냐하면 모든 경우를 확인해 줘야 하기 때문이다. (순서대로 담다가는 경로가 도중에 끊어질 수도 있다고 생각했다)
항공권의 2번째 요소는 다른 항공권의 1번째 요소라는 점을 활용해 주면 된다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<bool> isVisted;
vector<string> answer;
bool cmp(vector<string> &a, vector<string> &b)
{
    return a[1] < b[1];
}
void dfs(string port, vector<vector<string>> tickets)
{
    answer.push_back(port);
    for (int i = 0; i < tickets.size(); ++i)
    {
        if (isVisted[i])
            continue;
        if (tickets[i][0] == port)
        {
            isVisted[i] = true;
            dfs(tickets[i][1], tickets);
            if (answer.size() == tickets.size() + 1)
                return;
            isVisted[i] = false;
        }
    }
    if (answer.size() == tickets.size() + 1)
        return;
    answer.pop_back();
}
vector<string> solution(vector<vector<string>> tickets)
{
    sort(tickets.begin(), tickets.end(), cmp);
    isVisted = vector<bool>(tickets.size());
    dfs("ICN", tickets);
    return answer;
}

풀이

맵을 활용할까 싶었는데 1차원 bool 벡터를 사용하려면 vector의 형태를 유지해야 할 것 같았다.
방문한 곳은 다시 방문하지 않고 사이즈가 가득 찼을 때는 더 이상 탐색할 필요가 없으므로 반환해 준다.