LeetCode 1971. Find if Path Exists in Graph (Java)

문제 링크

The problem link : LeetCode 1971. Find if Path Exists in Graph

문제 요약

노드의 개수 n, 간선들이 연결되어있는지 알려주는 배열 edges, 출발지 source, 목적지 destination이 주어집니다.
해당 그래프에서 source와 destination이 연결되어있는지 확인하고, 연결되어있을 경우 true를 반환하세요.

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

문제 풀이

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        boolean[] ch = new boolean[n];

        for(int[] edge : edges) {
            int a = edge[0], b = edge[1];
            graph.computeIfAbsent(a, k->new ArrayList<Integer>()).add(b);
            graph.computeIfAbsent(b, k->new ArrayList<Integer>()).add(a);
        }

        return dfs(graph, ch, source, destination);
    }

    private boolean dfs(Map<Integer, List<Integer>> graph, boolean[] ch, int st, int end){
        if(st == end) return true;

        if(!ch[st]){
            ch[st] = true;
            for(int next : graph.get(st)){
                if(dfs(graph, ch, next, end)) {
                    return true;
                }
            }
        }        
        return false;
    }

}

DFS 또는 BFS를 활용해서 풀 수 있는 Graph문제 입니다.
위 코드는 DFS를 활용한 풀이법니다.

추가로 computeIfAbsent가 활용됐는데, putIfAbsent의 경우 key값이 없을 경우 value를 넣어주지만,
computeIfAbsent의 경우 key값이 없을 경우 Function을 연산한 결과를 넣어줍니다.

시간 복잡도

O(V+E)입니다.
(V=정점의 개수, E=간선의 개수)