[LeetCode] 797. All Paths From Source to Target

문제

방향 비순환 그래프(DAG)가 인접 리스트 graph로 주어진다. graph[i]는 노드 i에서 갈 수 있는 노드 목록이다. 노드 0에서 노드 n - 1까지 가는 모든 경로를 반환한다.

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

접근

"모든 경로"를 구해야 하므로 DFS로 끝까지 내려가며 경로를 전부 나열한다.

핵심은 방문 체크가 필요 없다는 점이다. 입력이 DAG로 보장되므로 사이클이 없고, 어떤 경로를 따라가도 같은 노드를 다시 만나지 않는다. 오히려 방문 체크를 하면 0 → 1 → 3과 0 → 2 → 3처럼 노드를 공유하는 경로를 놓친다.

1. 현재까지의 경로를 인자로 들고 DFS를 돈다.
2. 경로의 마지막 노드가 n - 1이면 결과에 담는다.
3. 마지막 노드의 이웃마다 경로를 복사해 이어 붙이고 재귀한다.

풀이

function allPathsSourceTarget(graph: number[][]): number[][] {
    const paths = [];

    const dfs = (visited: number[]) => {
        const node = visited.at(-1);
        if (node === graph.length - 1) {
            paths.push(visited);
        }
        for (let i = 0; i < graph[node].length; i++) {
            const nextNode = graph[node][i];
            dfs([...visited, nextNode])
        }
    }

    for (let i = 0; i < graph[0].length; i++) {
        dfs([0, graph[0][i]]);
    }

    return paths;
};

재귀마다 [...visited, nextNode]로 새 배열을 넘기기 때문에 되돌리는(pop) 과정이 없어도 경로가 서로 섞이지 않는다.

복잡도

• 시간: O(2^n * n). DAG에서 경로 수는 최대 2^(n-2)개이고, 경로 하나를 만드는 데 O(n)이 든다.
• 공간: 결과를 제외하면 재귀 깊이와 경로 복사본으로 O(n^2), 백트래킹으로 바꾸면 O(n).

n <= 15라서 지수 시간이어도 충분히 통과한다.

개선 포인트

1. 바깥 for문은 없어도 된다. dfs 안에서 이미 이웃을 순회하므로 시작점만 넘기면 된다.

dfs([0]);

2. 배열 복사 대신 백트래킹. 경로 배열 하나를 공유하면서 push/pop 하고, 도착했을 때만 복사한다.

function allPathsSourceTarget(graph: number[][]): number[][] {
    const paths: number[][] = [];
    const path = [0];

    const dfs = (node: number) => {
        if (node === graph.length - 1) {
            paths.push([...path]);
            return;
        }
        for (const next of graph[node]) {
            path.push(next);
            dfs(next);
            path.pop();
        }
    };

    dfs(0);
    return paths;
}

정리

• 모든 경로 나열 = DFS(백트래킹)
• DAG 보장 = 방문 체크 불필요, 넣으면 오답
• 경로를 복사해서 넘기면 pop이 필요 없고, 공유하면 pop이 필요하다