📍 1. 문제

LeetCode - Find if Path Exists in Graph

📍 2. 풀이

📌 2-1. 풀이 (dfs reculsive)

(1) 방법

dfs 와 재귀를 이용한 방법 사용.

(2) 코드

class Solution {
    public ArrayList<Integer>[] graph;
    public boolean[] visited;
    public boolean result = false;
    
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        
        graph = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        visited = new boolean[n];
        
        dfs(source, destination);
        return result;
    }
    public void dfs(int vertex, int des) {
        if(vertex == des) {
            result = true;
        }
        if(result == true) return;
        
        visited[vertex] = true;
        for(int e : graph[vertex]) {
            if(!visited[e]) {
                dfs(e, des);
            }
        }
    }
}

(3) 결과

📌 2-2. 풀이 (dfs, stack)

(1) 방법

dfs를 stack으로도 풀어보고 싶어서 풀어봄.

(2) 코드

class Solution {
    public ArrayList<Integer>[] graph;
    public boolean[] visited;
    
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        
        graph = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        visited = new boolean[n];
        
        return dfs(source, destination);
    }
    public boolean dfs(int vertex, int des) {
        Stack<Integer> stack = new Stack<>();
        stack.push(vertex);
        visited[vertex] = true;
        
        while(!stack.empty()) {
            int node = stack.pop();
            if(node == des) return true;
            visited[node] = true;
            
            for(int e : graph[node]) {
                if(!visited[e]) {
                    stack.push(e);
                }
            }
        }
        return false;
    }
}

(3) 결과

📌 2-3. 풀이 (bfs, queue)

(1) 방법

bfs 방식으로도 풀어봄. queue를 이용.

(2) 코드

class Solution {
    public ArrayList<Integer>[] graph;
    public boolean[] visited;
    
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        
        graph = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        visited = new boolean[n];
        
        return bfs(source, destination);
    }
    public boolean bfs(int vertex, int des) {
        Queue<Integer> que = new LinkedList<>();
        que.add(vertex);
        visited[vertex] = true;
        
        while(!que.isEmpty()) {
            int node = que.poll();
            if(node == des) return true;
            for(int e : graph[node]) {
                if(!visited[e]) {
                    que.add(e);
                    visited[e] = true;
                }
            }
        }
        return false;
    }
}

(3) 결과

📍 3. 결론

bfs / dfs 의 시간복잡도 차이가 유의미