99클럽 코테 스터디 12일차 TIL, 완전탐색( All Paths From Source to Target)

1. 문제 정의

2. 문제 접근

dfs를 이용하여 완전탐색을 해주면 될 것 같다.

3. 문제 풀이

1. 0 인덱스 부터 시작하여 dfs시작한다.
2.  lastIndex가 current Index랑 같은 경우 결과를 더해준다.

4. 코드

class Solution {
     List<List<Integer>> ans;
     List<Integer> path;
     int lastIdx;

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        ans = new ArrayList<>();
        path = new ArrayList<>();
        lastIdx = graph.length - 1;
        path.add(0);

        dfs(graph, 0, path);

        return ans;
    }

    private void dfs(int[][] graph, int cur, List<Integer> path){
        if(cur == lastIdx){
            ans.add(new ArrayList(path));
            return;
        }

        for(int nextNode:graph[cur]){
            path.add(nextNode);
            dfs(graph,nextNode,path);
            path.remove(path.size()-1);
        }

      }
    }

5. 회고

처음에는 bfs로 풀려고 했다. 구현을 하다가 뇌정지가 와서 다시 dfs로 접근을 했다. 둘 다 할 수 있어야 할 것 같은데 문제마다 더 잘되는쪽이 있는 것 같아서 힘들다...