.leetcode(797. All Paths From Source to Target)

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

 

1. 2022/04/14 시도

소요시간: 23분(5분 구상, 18분 코딩)

class Solution {
    private List<List<Integer>> answers;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        answers = new ArrayList<>();
        
        int[] visited = new int[graph.length];
        Arrays.fill(visited, -1);
        
        
        dfs(graph, 0, graph.length-1, visited, 0);
        return answers;
    }
    
    public void dfs(int[][] graph, int s, int d, int[] visited, int counter) {
        if (s == d) {
            
            PriorityQueue<Integer> pq = new PriorityQueue<>(
                (o1, o2) -> {
                    if (visited[o1] > visited[o2]) {
                        return 1;
                    } else if (visited[o1] > visited[o2]) {
                        return -1;
                    }
                    return 0;
                }
            );
            for (int i=0; i<visited.length; i++) {
                if (visited[i] != -1) {
                    pq.offer(i);
                }
            }
            
            List<Integer> answer = new ArrayList<>();
            while (!pq.isEmpty()) {
                answer.add(pq.poll());
            }
            answer.add(s);
            answers.add(answer);
            return;
        }
        
        visited[s] = counter;
        for (int nbh: graph[s]) {
            if (visited[nbh] > -1) {
                continue;
            }
            dfs(graph, nbh, d, visited, counter+1);
        }
        visited[s] = -1;
    }
}

풀이 접근 과정

int[] visited를 만들어서 여기에 방문 순서대로 번호를 매긴다.

그리고 recursion의 끝은 원하는 마지막 노드에 도착했을때, 방문한 곳을 찾는다.(-1은 방문 안한 곳이다.)

방문 한 곳을 순서에 맞게 배열하기 위해 PriorityQueue를 사용했다.

순서대로 정렬이 되면 이를 answers에 저장한다.

같은 노드에서 다른 방식으로 도착 경로를 구할 수 있기에 visited[s] = -1로 초기화를 시켜준다.

 

느낀점

• 틀린 방법은 아닌데 복잡한 면이 있다. 배열을 씀으로써 리스트를 쓰는 것과 다르게 더 빠른 성능을 보장하고자 하였지만 실제로 저장로직에서 pq와 for문을 사용함으로써 의미없게 되었다.
• 이걸 리스트로 푼다면 훨씬 간단해진다. 그리고 위에 풀이는 원론적으로 풀어서 그렇지 지금 문제에 대해서는 더 간단하게 풀 수 있다.
  • 1, 먼저 여기는 종료 노드가 결정되어있다. graph.length-1이므로 이를 재귀변수로 넣지 않아도 된다.
  • 2, 리스트에서 마지막꺼만 추가하고 다시 빼고 하는 로직을 사용한다.
  • 3, 최종 답에 저장할때는 리스트를 새로 생성한다.
  • 아래 코드와 같다. 위의 코드와 달라보이지만 원리는 같다. 백트래킹이라고 할 수 있다.

class Solution {
    private List<List<Integer>> answers;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        answers = new ArrayList<>();
                
        List<Integer> visited = new ArrayList<>();
        visited.add(0);
        dfs(graph, 0, visited);
        return answers;
    }
    
    public void dfs(int[][] graph, int index, List<Integer> visited) {
        if (index == graph.length-1) {
            answers.add(new ArrayList<>(visited));
            return;
        }
        
        for (int nbh: graph[index]) {
            visited.add(nbh);
            dfs(graph, nbh, visited);
            visited.remove(visited.size()-1);
        }
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형