All Paths From Source to Target

노드마다 0 ~ n-1의 값을 가지는 directed acyclic graph (DAG)를 2차원 벡터로 받는다.

0번 노드에서 시작하여 n-1번 노드로 가는 모든 방법을 구하는 문제

class Solution {
public:
    void SearchDFS(int index, vector<vector<int>>& graph, unordered_set<int> &visited, vector<int> &path, vector<vector<int>> &result)
    {
        if (index == graph.size() - 1)
        {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < graph[index].size(); i++)
        {
            if (0 < visited.count(graph[index][i]))
            {
                continue;
            }

            path.push_back(graph[index][i]);
            visited.insert(graph[index][i]);

            SearchDFS(graph[index][i], graph, visited, path, result);

            path.pop_back();
            visited.erase(graph[index][i]);
        }

        return;
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        
        vector<int> path{};
        unordered_set<int> visited{};
        vector<vector<int>> result{};

        visited.insert(0);
        path.push_back(0);
        SearchDFS(0, graph, visited, path, result);

        return result;
    }
};