[leetcode] Find if Path Exists in Graph

문제

• 문제 링크
• 정수 n과 이차원 배열 edges가 주어진다. n개의 노드를 가진 양방향 그래프에서, 각 노드는 0에서 n-1로 라벨링 되어있고 edges는 노드들의 연결관계를 나타낸다. 각 노드는 최대 한 개의 간선으로 연결되어 있고, 자신을 참조하진 못한다. 그리고 노드를 나타내는 정수 source와 destination이 주어진다. 그래프 상에서 source에서 destination으로 가는 길이 있는지 구해야 한다.
• 제약 조건
  • 노드 개수: 1 <= n <= 2 * 10^5
  • 간선 개수: 0 <= edges.length <= 2 * 10^5
  • 중복된 간선은 없다.
  • 자신을 참조하는 간선은 없다.

풀이

풀기 전

• 주어진 간선으로 연결된 그래프를 그리고, DFS 또는 BFS를 사용해서 source->destination이 존재하는지 찾으면 된다.

코드

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (edges.length == 0 || source == destination)
            return true;

		// 노드는 0~n-1로 라벨링 되어 있으므로 배열의 인덱스로 노드를 찾을 수 있다.
        List<List<Integer>> nodes = new ArrayList<>();
        for (int i=0; i<n; i++)
            nodes.add(new ArrayList<>());

		// 서로 참조하는 간선을 연결한다.
        for (int[] edge : edges) {
            int n1 = edge[0];
            int n2 = edge[1];

            nodes.get(n1).add(n2);
            nodes.get(n2).add(n1);
        }

		// source에서부터 BFS로 탐색을 진행한다.
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(source);
        visited[source] = true;
        while (!q.isEmpty()) {
            int now = q.poll();

            for (int next : nodes.get(now)) {
                if (visited[next])
                    continue;
                if (next == destination)  // destination을 찾으면 true를 반환한다.
                    return true;
                q.add(next);
                visited[next] = true;
            }
        }
        return false;  // 탐색이 종료됐다는 건 destination을 못 찾았다는 의미이므로 false를 반환한다.
    }
}

푼 후

• 모든 그래프를 최대 한 번씩 탐색하기 때문에 시간 복잡도는 O(n)이다. 모든 노드가 서로 연결되어 있다면, 연결 관계를 나타내는 이차원 배열이 n^2만큼 차게 된다. 따라서 공간 복잡도는 O(n^2)이다.