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

1. 링크 프로그래머스 여행경로

2. 풀이

먼저 다음 두가지 조건을 눈여겨 볼 필요가 있습니다.

• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

첫번째 조건으로 부터 얻을 수 있는 것은 알파벳 순서가 앞서는 경로가 답이 되므로 오름차순으로 정렬해야한다는 것을 알 수 있습니다.

두번째 조건으로 얻을 수 있는 것은 dfs로 탐색을 할 경우, 모든 도시를 방문할 수 없을 정도로 depth가 짧을 경우에는 다시 탐색한다는 것을 알 수 있습니다.

그리고 depth가 짧아서 다시 탐색을 하는 경우에는 다시 탐색을 시작하는 노드 이후의 노드를 모두 다시 탐색이 가능한 상태로 만들어 주어야합니다.

예를 들어 위의 그래프에서 2-3-5-9-8을 방문했는데 답이 모든 도시를 방문을 못했다면 3-5-9-8을 전부 탐색이 가능한 상태로 만들어주고 2에서 선택할 수 있는 다른 길을 선택을 하는 것입니다. ex) 2-5-3, 2-5-9-6-4-1

그렇게 하기 위해서 함수 스택을 활용한 dfs를 사용을 했습니다.

used[i] = true;
dfs_reculsive(tickets, used, path, count + 1);
if (false == path.back().empty())
	return;
used[i] = false;

3. 코드

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

using namespace std;

void dfs_reculsive(vector<vector<string>>& tickets, vector<bool>&used, vector<string>& path, int count)
{
    for (int i = 0; i < tickets.size(); i++)
    {
        if (tickets[i][0] == path[count - 1])
        {
            if (true == used[i])
                continue;
            path[count] = tickets[i][1];
            used[i] = true;
            dfs_reculsive(tickets, used, path, count + 1);
            if (false == path.back().empty())
                return;
            used[i] = false;
        }
    }
}

vector<string> dfs(vector<vector<string>>& tickets, const string start)
{
    int size = tickets.size();
    vector<bool> used(size, false);
    vector<string> path(size + 1);
    path[0] = start;
    dfs_reculsive(tickets, used, path, 1);
    return path;
}

vector<string> solution(vector<vector<string>> tickets) 
{
    sort(tickets.begin(), tickets.end());
    vector<string> path = dfs(tickets, "ICN");
    return path;
}