DFS와 백트래킹을 활용한 알고리즘 문제풀이

오늘 푼 문제: all-paths-from-source-to-target

입출력

• 입력: 각 정점과 연결된 다른 정점들을 담은 2차원 배열이 주어집니다.
• 출력: 0번 정점에서 n-1번 정점으로 이어지는 모든 경우를 2차원 배열로 반환합니다.

예제 코드

import java.util.*;

class Solution {
    static int n;
    static int[] ch;
    static List<List<Integer>> answer;
    static void DFS(int[][] graph, int v, Stack<Integer> stack) {
        if (v == n) {
            answer.add(new ArrayList<>(stack));
        } else {
            for (int nv : graph[v]) {
                stack.push(nv);
                DFS(graph, nv, stack);
                stack.pop();
            }
        }
    }
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        n = graph.length - 1;
        answer = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        DFS(graph, 0, stack);
        return answer;
    }
}

• 처음에는 배열로 해서 이동한 정점을 0/1로 비교했습니다.
• 하지만 그럴 경우 이동한 순서대로 입력할 수 없었습니다.
• 그래서 Stack을 사용하여 매 정점마다 이동 정점을 저장하였습니다.
• n - 1번 정점에 가는 경우 Stack을 ArrayList로 바꾸어 정답 ArraayList에 입력합니다.

회고

• 오늘은 몸이 좋지 않아서 구현 기능 정리를 작성하지 않고 바로 풀었습니다.