방향성을 가지면서 사이클이 없는 그래프, 즉 방향 비순환 그래프(DAG)에 N개의 노드가 있다고 가정해 봅시다. 우리의 목표는 노드 0에서 노드 N-1까지 이어지는 가능한 모든 경로를 찾아, 어떤 순서로든 반환하는 것입니다.
그래프는 다음과 같은 형태로 주어집니다. 노드 번호는 0, 1, ..., graph.length - 1이며, graph[i]는 간선 (i, j)가 존재하는 모든 노드 j의 목록을 담고 있습니다.
예를 들어 입력이 [[1,2], [3], [3], []]와 같다면, 출력은 [[0,1,3], [0,2,3]]이 됩니다. 즉, 노드 0에서 출발하여 노드 3에 도착하는 두 가지 경로가 존재하는 것입니다.
문제 해결 접근 방법
이 문제는 깊이 우선 탐색(DFS) 기반의 재귀적 백트래킹으로 자연스럽게 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.
결과를 저장할 2차원 배열
res를 하나 만듭니다.solve라는 재귀 메서드를 정의합니다. 이 메서드는 그래프(graph), 현재 노드(node), 목표 노드(target), 그리고 지금까지의 경로를 담는 임시 배열(temp)을 매개변수로 받습니다.현재 노드를 temp 배열에 삽입합니다.
현재 노드가 목표 노드라면, 완성된 경로인 temp를 res에 삽입한 후 재귀를 종료하고 돌아갑니다.
i를 0부터 graph[node]의 크기 - 1까지 반복하면서, 다음 노드에 대해
solve(graph, graph[node][i], target, temp)를 재귀적으로 호출합니다.메인 함수에서 빈 temp 배열을 생성한 뒤,
solve(graph, 0, graph.size() - 1, temp)를 호출하여 탐색을 시작합니다.최종적으로 res를 반환합니다.
C++ 구현 예제
아래 구현 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
void solve(vector < vector <int> >& graph, int node, int target, vector <int>temp){
temp.push_back(node);
if(node == target){
res.push_back(temp);
return;
}
for(int i = 0; i < graph[node].size(); i++){
solve(graph, graph[node][i], target, temp);
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector <int> temp;
solve(graph, 0, graph.size() - 1, temp);
return res;
}
};
main(){
vector<vector<int>> v = {{1,2},{3},{3},{}};
Solution ob;
print_vector(ob.allPathsSourceTarget(v));
}입력
[[1,2],[3],[3],[]]
출력
[[0, 1, 3],[0, 2, 3]]
동작 원리 정리
위 코드의 핵심은 solve 함수의 재귀 구조입니다. 노드 0에서 출발해 인접 노드를 하나씩 따라가며 경로를 확장하고, 목표 노드(N-1)에 도달할 때마다 해당 경로를 결과 배열에 저장합니다. 그래프가 비순환이므로 무한 루프에 빠질 위험 없이 모든 경로를 안전하게 탐색할 수 있습니다. 시간 복잡도는 최악의 경우 지수적으로 증가할 수 있지만, DAG 구조상 실제 문제 환경에서는 충분히 효율적으로 동작합니다.