[LeetCode] - 797. All Paths From Source to Target(C/C++)

문제 링크 : https://leetcode.com/problems/all-paths-from-source-to-target/

[문제 설명]

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

 

Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2:

Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

 

Constraints:

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i (i.e., there will be no self-loops).
• All the elements of graph[i] are unique.
• The input graph is guaranteed to be a DAG.

---

[문제 풀이]

위 문제는 0 ~ n-1까지의 경로를 모두 리턴하면 되는 문제다.

입력으로 주어지는 DAG(Directed Acyclic Graph)를 보장한다.

DAG라는것은 이전에 위상정렬 포스팅에서 설명했던 내용이다.

[Algorithm] - Topology Sort(위상정렬)

 

간단하게 설명하자면, 루프가 생기지 않고 단방향의 단선을 가지 그래프라는 것이다.

루프는 간단히 시작 노드에서 다른 노드를 거쳐서 다시 시작 노드로 오는 상황을 얘기할 수 있겠다.

 

위의 조건들로 인해서 이 문제는 간단하게 풀수있게된다.

 

시작 노드는 0번 노드로 고정되어있고, 경로의 끝인 노드는 n-1 노드이다.

0번 노드로 시작해서 dfs를 진행하면 된다.

 

매 dfs 탐색이 종료될때의 조건을 잘 설정해야한다.

0 -> n-1로 바로 가는 선이 있다면 이 또한 경로에 포함되어야한다.

따라서 재귀의 종료 조건을 현재 탐색하는 노드가 n-1이라면 answer에 넣어주고 종료해주면 된다.

 

모든 탐색을 끝낸후 answer 벡터를 리턴 해주면 된다.

[코드]

[GitHub]

GitHub - EGyeom/ProblemSolving

vector<bool> isVisited;

void dfs(vector<vector<int>>& answer, vector<vector<int>>& graph, int cur, vector<int>& temp)
{
    if(cur == graph.size() -1)
    {
        answer.push_back(temp);
        return;
    }
    for(int next : graph[cur])
    {
        if(isVisited[next]) continue;
        isVisited[next] = true;
        temp.push_back(next);
        dfs(answer,graph,next,temp);
        temp.pop_back();
        isVisited[next] = false;
    }
}

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        isVisited.resize(graph.size(), 0);
        vector<vector<int>> answer;
        vector<int> temp;
        temp.push_back(0);
        dfs(answer, graph, 0, temp);
        return answer;
    }
};