99클럽 코테 스터디 14일차 TIL + [LeetCode] 797. All Paths From Source to Target JAVA풀이/DFS

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

DFS

재귀

그래프

 

 

2. 오늘의 학습 문제 

---

문제

---

 

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

 

 

 

코드

---

import java.util.*;

class Solution {
    static List<List<Integer>> answer ;
    static int [][] mstGraph ;
    static int target;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        mstGraph=graph;
        target=graph.length;
        answer=new ArrayList<>();
        List<Integer> temp = new ArrayList<>();

        DFS( graph[0], temp, 0);
        return answer;
    }

    static public void DFS ( int[] graph, List<Integer> temp, int val){
        List<Integer> currentPath = new ArrayList<>(temp); //새로운 리스트 선언하여 현재 temp리스트 복사

        currentPath.add(val);
        if(val== target-1 ){ //타겟 도달시 answer에 add
            answer.add(currentPath);
        }
        else{
            for (int i : graph){ //재귀 DFS
                DFS(mstGraph[i], currentPath, i );
            }

        }

    }
}

 

 

그래프 문제였다.

1. 정수 리스트 temp를 선언하고 DFS로 그래프를 재귀적으로 순회하며 노드의 값을 하나씩 담는다.

2. DFS 함수 호출시 새로운 currentPath 리스트에 인자로 전달한 temp 리스트를 복사하고, currentPath에 val값을 추가한다.

3. 만약 노드의 끝까지 도달한 경로가 생성된다면 answer에 currentPath를 add한다.

4. DFS 함수가 모두 끝나면, allPathSourceTarget함수에서 answer를 리턴한다.

 

* 처음에는 DFS 함수에 인자로 전달한 temp를 재귀함수시 동일한 것을 전달하여, answer에 모두 동일한 값의 temp가 추가되는 일이 발생했다. (중복) 따라서 DFS 함수를 호출하면 currentPath 리스트를 새롭게 선언하여 현재 temp리스트를 복사하고, 조건에 맞다면 add하는 방법을 선택하였다. 

 

3. 오늘의 회고

---

 

• DFS 방법으로 풀었는데, 다음번에는 BFS 방법으로 풀어보려고 한다.
• 동일한 리스트를 인자로 전달할때 생기는 중복오류를 해결하기 위해, 다른 새로운 리스트를 선언하고 값을 복사하여 넣는 방법을 숙지해야겠다.