뒤죽박죽 코딩 이야기

2022년 12월 30일 금요일 - 22년이 끝나간다....

오늘 올려볼 문제는 797번 All Paths From Source to Target 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

생각보다는 쉽게 풀렸당

입력

사진에서도 볼 수 있듯이 int 2차원 배열 1개가 입력으로 들어온다.

풀이 및 코드

주어진 DAG에서 0부터 n-1 노드까지 갈 수 있는 방법들을 구해서 리턴하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

dfs 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    int n;
    int[][] g;
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        g = graph;
        n = g.length;
        solve(0, new Stack<Integer>());
        return result;
    }
    
    public void solve(int index, Stack<Integer> s) {
        s.push(index);
        
        if(index == n - 1) {
            result.add(new ArrayList<Integer>(s));
            s.pop();
            return;
        }
        
        for(var num: g[index]) {
            solve(num, s);
        }
        
        s.pop();
    }
}

제출 화면

이제 하루하고 몇시간 뒤면 2023년이 된다는게 신기하다....

안녕~

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.