99클럽 코테 스터디 14일차 TIL All Paths From Source to Target

 

https://leetcode.com/problems/all-paths-from-source-to-target/description/

 

 

 

eetcode

797. All Paths From Source to Target

 

1. 문제 및 접근

 

DAG, (방향이 있고사이클이 없는 비순환 알고리즘이란 뜻)

방향을 가진 노드들로 0부터n-1까지 갈 수 있는 방법을  return

배열이 주어지면 index가 그 수가 되고, 값이 갈 수 있는 방향의 수를 나타냄

모든 경우의 수를 다 가져야 하니까, 기록해주면서 dfs 호출 ?

 

기저 조건을 어떻게 잡아줄까... index를 늘려주면서 그 index에 접근하면 ?

 

 

제한 사항

 

 

 

 

 

2. DAG ?

 

 

 

DAG(Directed Acyclic Graph)는 순환그래프가 아닌 비순환 그래프

즉, DAG알고리즘에서는 순환하는 싸이클이 존재하지 않고, 일방향성만 가지는 것이 포인트

 

 

그래프는 비선형 자료구조이므로 보통은 정렬할 수 없지만 DAG로 위상 정렬(Topological Sort)이 가능해짐

 

 

사이클이 없어 작업의 우선순위를 표현하기 좋다.

 

 

예를 들어 여러 작업이 존재하고, 선행되어야 하는 작업들이 있다면 하나의 작업을 실행하려면,

그에 맞는 선행 작업들이 우선순위로 존재하기 때문

 

 

 

https://yonghwankim-dev.tistory.com/222

 

 

 

 

3. 풀이

 

 

public class allPathsFromSourcetoTarget {

    //leetcode
    // 797. All Paths From Source to Target
    // DAG, (방향이 있고사이클이 없는 비순환 알고리즘이란 뜻)
    //방향을 가진 노드들로 0부터n-1까지 갈 수 있는 방법을  return
    //배열이 주어지면 index가 그 수가 되고, 값이 갈 수 있는 방향의 수를 나타냄
    // 모든 경우의 수를 다 가져야 하니까, 기록해주면서 dfs 호출 ?
    // hashmap으로 생각했는데 중복때문에 pass
    // 기저 조건을 어떻게 잡아줄까... index를 늘려주면서 그 index에 접근하면 ?
    
    private static int n;

   

    private List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        n = graph.length;

        List<List<Integer>> answer = new ArrayList<>(); // 경로들이 다 담긴 정답리스트
        List<Integer> route = new ArrayList<>(); // 정답인 하나의 경로
        route.add(0); // 첫 경로 시작은 0
        dfs(0, graph, route, answer);





        return answer;

    }

    private void dfs(int index, int[][] graph, List<Integer> route, List<List<Integer>> answer) {


        if (index == n - 1) { // 마지막 까지 도착했다면 ?
            // 마지막을 어떻게 표현할지 하다가 그냥 graph의 level로 처리
            answer.add(new LinkedList<>(route));
            return;
        }

        for (int j : graph[index]) {
            route.add(j); // index에서 갈 수 있는 수들을 돌면서 각각의 루트에 추가
            dfs(j, graph, route, answer); // 추가한 후 그 수로 이동해서 계속 ~
            route.remove(route.size() - 1); //백트레킹을 위해 다시 호출한 idx에서 다음 j번째 탐색
        }
    }

 

 

 

3-1 List 선언 

 

 

 

 

n-1 값으로 기저 조건 체크하기 위해 static

 

하나의 경로를 담을 route와 route들이 모여서 answer list를 초기화

 

route에서 시작은 0부터 백트레킹을 하니까 9 담아주고,

 

dfs 호출

 

 

 

 

3-2  DFS 기저조건

 

 

 

 

탈출 조건으로 index가 graph의 길이만큼 된다면 

 

정답리스트에 이때까지 담긴 하나의 완성된 route를 더해주고, return;

 

 

 

3-3 DFS 백트레킹

 

 

2차원 배열 graph에서 [index] 번째의 요소들을 j로 선언하고,

 

그 index에서 갈 수 있는 j를 순차적으로 route에 추가해줌 

 

dfs에 index를 그 j 값으로 호출해주고, 하나의 경로가 담기고 호출이 끝난다면 

 

백트레킹을 위해 차례대로 remove해줘 다시 index0의 다음 j번째의 수로 for 문 수행

 

 

 

 

성공!

 

 

4. 마무리

 

 

 

사실 처음 DAG 자체를 처음 보는 용어라서 엄청 어려울줄 알고 긴장했으나, 크게 어렵지 않은 개념이였다.

 

리트 코드가 너무 익숙치 않아 input을 이해하느라 시간이 많이 걸리고 거기서 DAG에 들어 오는 게 

 

index 별로 갈 수 있는 값들이라는 것도 몰랐던 거 보면 그냥 graph를 모른다고 해야한다..

 

문제 자체는 쉬웠으나, 2차원 배열의 j값이 무작위로 들어 오는 걸

 

foreach로 푼다는 걸 바로 못 떠올라서 요새 foreach를 많이 쓰고 있다..

 

(증감식 없이 인자의 수만큼 돌 수 있어서 간편)