.leetcode(1971. Find if Path Exists in Graph)

https://leetcode.com/problems/find-if-path-exists-in-graph/

 

1. 2022/04/14 시도

소요시간: 30분

// dfs
class Solution {
    private boolean found = false;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }

        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i=0; i<n; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        
        for (int[] edge: edges) {
            adjacencyList.get(edge[0]).add(edge[1]);
            adjacencyList.get(edge[1]).add(edge[0]);
        }
        
        boolean[] visited = new boolean[n];
        
        dfs(adjacencyList, visited, source, destination);
        
        return found;
    }
    
    private void dfs(List<List<Integer>> adjacencyList, boolean[] visited, int source, int destination) {
        if (source == destination) {
            found = true;
            return;
        }
        
        visited[source] = true;
        for (Integer nbh: adjacencyList.get(source)) {
            if (visited[nbh]) {
                continue;
            }

            dfs(adjacencyList, visited, nbh, destination);
        }
    }
}

풀이 접근 과정

그래프에서 공부했던 인접노드 저장방식으로 접근했다.

그리고 found라는 전역변수를 써서 바로 찾으면 리턴되도록 코딩했다.

 

느낀점

• 이는 모든 경우의 수를 찾는게 아니라 하나만 찾아도 되기때문에 visisted[]를 써서 하나씩 노드를 지워가면 비교적 쉽게 풀 수 있다.
• dfs-recrusion이 풀리면 stack으로도 풀리니 그렇게 다시 한번 풀었다. 한번 재귀로 풀어두면 이걸 iterative의 dfs로 푸는건 어렵지 않다.

class Solution {
    private boolean found = false;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }

        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i=0; i<n; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        
        for (int[] edge: edges) {
            adjacencyList.get(edge[0]).add(edge[1]);
            adjacencyList.get(edge[1]).add(edge[0]);
        }
        
        boolean[] visited = new boolean[n];
        Stack<Integer> stack = new Stack<>();
        stack.add(source);
        
        boolean found = false;
        while(!stack.isEmpty()) {
            int node = stack.pop();
            if (node == destination) {
                return true;
            }
            visited[node] = true;
            for (int nbh: adjacencyList.get(node)) {
                if (visited[nbh]) {
                    continue;
                } 
                
                stack.push(nbh);
            }
        }
        return false;
    }
}

• 전체 경로를 구해야하는 경우가 있을 때는 어떻게 접근하면 좋을까 하다가 boolean[] visisted를 int[]로 형변환씨키고, 매번 재귀가 일어날 때, 인덱스 번호를 증가시킴으로써 배열에 순서를 기록해두는것도 하나의 방법일거 같았다. 아래와 같이 풀 수 있다.
  • 마지막 번호를 얻는 방식은 동일하다.
  • 배열에 순서가 적혀있는 걸 순서대로 출력하기 위해, PriorityQueue를 사용했다.
  • 타임아웃이 나서 실패했다.

class Solution {
    private List<List<Integer>> foundedList;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }
        
        foundedList = new ArrayList<>();
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i=0; i<n; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        
        for (int[] edge: edges) {
            adjacencyList.get(edge[0]).add(edge[1]);
            adjacencyList.get(edge[1]).add(edge[0]);
        }
        
        int[] visited = new int[n];
        Arrays.fill(visited, -1);
        
        dfs(adjacencyList, visited, 0, source, destination);
        
        return foundedList.size()>0;
    }
    
    private void dfs(List<List<Integer>> adjacencyList, int[] visited, int count, int source, int destination) {
        if (source == destination) {
            PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
                if (visited[o1] > visited[o2]) {
                    return 1;
                } else if (visited[o1] < visited[o2]) {
                    return -1;
                }
                return 0;
            }); 

            List<Integer> answer = new ArrayList<>();
            for (int i=0; i<visited.length; i++) {
                if (visited[i] == -1) {
                    continue;
                }

                pq.offer(i);
            }
            while (!pq.isEmpty()) {
                answer.add(pq.poll());
            }
            foundedList.add(answer);
            return;
        }
        
        visited[source] = count;
        for (Integer nbh: adjacencyList.get(source)) {
            if (visited[nbh] >= 0) {
                continue;
            }

            dfs(adjacencyList, visited, count+1, nbh, destination);
        }
        visited[source] = -1;
    }
}

---

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

반응형