99클럽 코테 스터디 14일자 TIL + all-paths-from-source-to-target

문제 출처

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

학습 키워드

DFS/BFS

시도 방법

BFS를 활용하였고, 추가되는 배열에 대한 마지막 값을 기준으로 방향이 더 있으면 큐에 추가함
추가한 마지막 값이 해당 그래프의 마지막 값과 동일하면 값을 결과에 추가하였음

내가 작성한 코드

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {

        List<List<Integer>> result = new ArrayList<>(); 
        Queue<List<Integer>> q = new LinkedList<>();
        
        q.add( List.of(0));  // ArrayList<Integer> 로 [0] 이 들어감
        
        while(!q.isEmpty()) {

            List<Integer> arr = q.poll(); 
            int lastNum = arr.get(arr.size() -1); //큐에서 추출한 List의 마지막 값 상태 확인

            if(lastNum == graph.length-1 ) { //마지막 값이 그래프의 마지막 값이 동일하면 결과 추가
                result.add(arr);
                continue; 
            }

            for(int i = 0 ; i<graph[lastNum].length; i++) {
                ArrayList<Integer> tmp = new ArrayList<>(arr); 
                tmp.add(graph[lastNum][i]); 
                q.add(tmp);                 
            }
        }


        return result;
    }
}

코드설명

queue에 [0] 이 있고 graph = [[1,2],[3],[3],[]] 일 때를 예시로 들어보자.

while(!q.isEmpty()) {

    List<Integer> arr = q.poll(); 
    int lastNum = arr.get(arr.size() -1); //큐에서 추출한 List의 마지막 값 상태 확인

    if(lastNum == graph.length-1 ) { //마지막 값이 그래프의 마지막 값이 동일하면 결과 추가
        result.add(arr);
        continue; 
    }

    for(int i = 0 ; i<graph[lastNum].length; i++) {
        ArrayList<Integer> tmp = new ArrayList<>(arr); 
        tmp.add(graph[lastNum][i]); 
        q.add(tmp);                 
    }
}

첫번째 회전

큐에서 poll()을 하면 [0] 인 리스트가 출력된다.
이 리스트의 마지막 값은 0이다. 그래서 graph[0] 을 찾아 방향이 있는지 확인하고
있으면 이를 추가한 새로운 리스트를 큐에 등록한다.

예) graph[0] 에는 [1,2] 가 있음
큐에 [0,1] 적재 //기존값 + 1
큐에 [0,2] 적재 //기존값 + 2 를 추가

두번째 회전

큐에서 poll()을 하면 [0,1] 인 리스트가 출력된다.
이 리스트의 마지막 값은 1이다. 그래서 graph[1] 을 찾아 방향이 있는지 확인했다.

예) graph[1] 에는 [3] 이 있음
따라서 큐에 [0,1,3] 적재 // 기존값 + 3 을 했다.

세번째 회전

큐에서 poll()을 하면 [0,2] 인 리스트가 출력된다. (이제 큐에는 [0,1,3]만 있음)
이 리스트의 마지막 값은 2이다. 그래서 graph[2] 를 탐색해본다.

예) graph[2] 에는 [3] 이 있음
따라서 큐에 [0,2,3] 적재 //기존값 + 3 을 했다. (이제 큐에는 [0,1,3] , [0,2,3] 이 있음

네번째 회전

큐에서 poll() 하면 [0,1,3] 인 리스트가 나온다. 마지막이 3 (그래프 마지막) 과 동일하므로 결과인 result에 [0,1,3]을 추가하고 continue 한다.

다섯번째 회전

큐에서 poll() 하면 [0,2,3] 인 리스트가 나온다. 같은 이유로 result에 [0,2,3] 추가하고 continue 한다.

여섯번째 회전

큐가 비었으므로 종료한다.

출력결과

새롭게 알게된 점

이제보니 leetcode는 해결 후 시간이 얼마 걸렸는지를 그래프로 보여준다.
내 코드의 경우 ArrayList를 반복적으로 생성하다보니 시간이 좀 걸린 것 같다.

2ms가 나온 케이스 코드를 분석하고 오늘 정리를 마쳐야 겠다.

2ms 케이스

BFS가 아니라 DFS 방식으로 풀이한 것으로 보인다.
먼저 path에 0을 추가해서 helper라는 메서드로 재귀실행을 하고 있다.
이후 로직은 비슷한 것 같다.

아마 DFS 와 BFS 의 차이인거 같은데
BFS는 DFS에 비해 큐에서 꺼내고 제거하는 과정에서 추가적인 오버헤드가 있을수 있다고 설명한다.

결론은 둘 다 사용해볼 수 있고, 각 문제 특성에 따라 다를 수 있다는 것이다.

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> paths = new ArrayList();
        List<Integer> path = new ArrayList();
        path.add(0);
        helper(graph, 0, paths, path);
        return paths;
    }
    
    void helper(int[][] graph, int current, List<List<Integer>> paths, List<Integer> path) {
        if (current == graph.length - 1) {
            paths.add(new ArrayList(path));
            return;
        }
        
        for (int next : graph[current]) {
            path.add(next);
            helper(graph, next, paths, path);
            path.remove(path.size() - 1);
        }
    }
}

다음에 풀어볼 문제 - ??

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL