[プログラマー]旅行コース

10868 ワード
DFS トラベルパスC++ プログラマー旅行コース プログラマー旅行コース テキストリンク

[プログラマー]旅行コース


1. リンクプログラマトラベルパス


2.解答


まず、次の2つの条件に注意してください.
  • 可能なパスが2つ以上ある場合は、アルファベット順にリードするパスを返します.
  • すべての都市へのアクセスは許可されていません.
    • 最初の条件から得られるのは,アルファベット順にリードする経路が答えとなるため,昇順に並べ替えなければならないことである.
    2つ目の条件は、dfsを使用してナビゲーションを行う場合、深さが足りない(すべての都市にアクセスできない)場合は、再度ナビゲーションすることです.
    深度が短いために再度ナビゲーションを行う場合は、ナビゲーションを再開したノードの後にあるすべてのノードをナビゲーション可能にする必要があります.

    たとえば、上記のグラフで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;
}
    DB学習3週目
    Selenium+Java(10)Seleniumの一般的な方法