[Leetcode] 797. All Paths From Source to Target (C++)

문제

797. All Paths From Source to Target

코드

class Solution {
public:
    vector<vector<int>> answer;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<bool> visited(graph.size(), false);
        
        visited[0] = true;
        dfs(graph, visited, 0, graph.size(), {0});
        
        return answer;
    }
    
    void dfs(vector<vector<int>>& graph, vector<bool>& visited, int idx, int target, vector<int> cur){
        if (target-1 == idx){
            answer.push_back(cur);
            return;
        }
        for (int i = 0; i < graph[idx].size(); i++){
            if (visited[graph[idx][i]]) continue;
            cur.push_back(graph[idx][i]);
            visited[graph[idx][i]] = true;
            dfs(graph, visited, graph[idx][i], target, cur);
            cur.pop_back();
            visited[graph[idx][i]] = false;
        }
    }
};

접근

기본적으로 그래프라고 생각해서 dfs로 풀릴 것 같다는 생각이 들었다. 0 ~ n-1까지 가는 것이기 때문에 먼저 0번은 방문처리해주고 dfs를 시작했다. n-1 까지 도달한다면 경로를 answer 에 추가하고 return 하여 마무리한다.