Leetcode - 1971. Find if Path Exists in Graph

몇 코딩테스트를 보면서 지난 알고리즘의 추억들이 떠올랐다. 그 중 단연 가장 많이 풀었던 그래프 유형. 그 중에서도 가장 많이 활용했던 DFS. 오랜만에 만나서 반가웠다.

이 문제는 주어진 정점들과 간선들을 통해 시작점 ~ 끝점까지 갈 수 있는지를 true or false로 반환하면 되는 간단한 그래프 문제이다.

이전에는 주로 dx, dy를 활용해 DFS를 구현했는데 나이도 시간도 경력도 쌓인 이 시점에 더 나은 방법을 구현해보고 싶었고 ArrayList를 활용해 더욱 간결한 코드로 구현해보았다.

//1971. Find if Path Exists in Graph
class Solution {
    static boolean isVisited[];
    static ArrayList<Integer> arr[];
    static int end;

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        
        arr = new ArrayList[n];
		isVisited = new boolean[n];
		end = destination;

        boolean result = false;

		for (int i = 0; i < n; i++) {
			arr[i] = new ArrayList<>();
		}

		for (int[] edge : edges) {
			int a = edge[0];
			int b = edge[1];

			arr[a].add(b);
			arr[b].add(a);
		}

		return dfs(source);
    }

    public boolean dfs(int s){
        if(s==end){
			return true;
		}

        isVisited[s] = true;
		
		for(int i : arr[s]){    // arr[s] 배열의 각 숫자들을 하나씩 확인
			if(!isVisited[i]){
				if(dfs(i)){     // 경로를 만나면 바로 true 반환
                    return true;
                }
			}
		}
        return false;
    }
}

포인트: 각 정점과 이어지는 정점을 리스트로 만들어서 각각 연결됨을 표현해준다.