[LeetCode] 1971. Find if Path Exists in Graph

1971. Find if Path Exists in Graph

Easy

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

 

Example 1:

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

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

 

Constraints:

• 1 <= n <= 2 * 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= source, destination <= n - 1
• There are no duplicate edges.
• There are no self edges.

---

문제 풀이

• 그래프가 주어지고, 출발점과 도착점이 주어진다. 
• 그래프는 간선들로 이루어져있는데 양방향 그래프이다. 
• edges 배열은 한 노드에서 다른 노드로 연결된 간선을 의미한다. 
• 출발점에서 도착점까지 이동할 수 있는지를 구해야한다.
• 그래프 문제이기 때문에 완전탐색으로 접근할 수 있으며, 문제 제한을 봤을때 최악의 경우 2 x 10^5 이다. 
• 모든 노드를 DFS, BFS로 탐색한다면 노드 개수만큼의 O(N) 시간 복잡도일 것이다. 
• 그리고 노드 뿐만 아니라 모든 간선을 탐색해야 연결이 어떻게 되있는지 알 수 있기 때문에 최종 시간 복잡도는 O(N + M)이다. 

DFS

• 리스트 딕셔너리로 양방향 간선들을 모두 넣는다. 
• 한번 방문한 노드를 처리해주기 위해 n크기의 visited 배열을 0으로 초기화한다. 
• 재귀 함수를 만들때 종료 조건은 현재 노드 숫자가 종료번호이거나 방문 했던 노드라면 리턴을 해야한다. 
• 목적지일 경우에는 True를 리턴한다. 
• visited 배열에 해당 노드에 방문한 기록을 해주며, 현재 노드에 연결되어있는 간선들을 탐색한다.
• dfs 재귀함수의 종료조건에서 답으로 True가 리턴되면, 그자리에서 True를 리턴하면서 끝낸다. 
• 한번 True가 발생하면 전 재귀함수 혹은 후 재귀함수에서 모두 리턴 처리가 된다. 
• 반복문이 끝나고 나면 해당 노드의 간선에 대한 탐색이 끝났기 때문에 False를 리턴한다. 
• False가 특정 상황에서 리턴이 되면 dfs는 계속 진행된다.

Union-find

• 유니온 파인드를 사용하여 노드들의 그룹 여부를 알 수 있다. 
• 이를 이용해서 같은 그룹에 시작과 도착점이 있다면 정답이다. 
• 유니온 파인드를 개선해서 사용하면 간선 크기만큼의 m으로 모든 그룹을 만들고 나서 find 함수를 사용한다.
• 그때 O(a(n)) 시간복잡도인데, a(n)은 n보다 작은 숫자라고 생각하는게 편하다. 
• 왜냐하면 완성된 그룹 자료구조에서 find 함수는 O(1)만에 부모 노드를 찾을 수 있기 때문이다. 
• 우선, 부모 배열을 자기 자신의 번호로 초기화한다. 
• 자기 자신이 부모라면 그 노드는 아무 그룹에도 해당되지 않음을 의미한다. 
• find함수는 재귀함수를 사용하는데, 만일 찾는 노드의 부모가 현재 노드가 아니라면 find 함수를 재귀호출한다. 
• 그리고 함수가 종료될때 현재 재귀함수호출 상황의 부모노드를 리턴한다. 
• 결과적으로 첫 노드 번호의 부모노드를 찾는데, 재귀호출시 리턴되는 부모노드를 현재 재귀호출 상태의 부모 노드 배열에 저장한다.
• 최종 부모 노드, 즉 최상위 부모 노드가 한 그룹의 부모로 통일되어 저장된다. 
• Union 함수는 매개 변수 두개를 두개의 노드를 연결하려는 의도로 만든다. 
• 우선 각각 노드의 부모를 찾아 가져온다. 
• 그리고 만일 노드들의 부모가 다르다면 첫 노드의 부모를 두번째 노드의 부모로 저장한다.
• 함수를 다 만들었다면 모든 간선들에 대해 Union 함수를 호출하여 부모 노드 배열을 채운다. 
• 그룹이 완성되면 시작 노드번호와 도착 노드번호의 부모 노드를 find로 찾는다. 
• 두개의 노드에 대한 부모 노드를 비교했을때, 같으면 그룹이고 다르면 그룹이아니다. 
• 즉, 출발지와 도착지는 같은 그룹일때 연결되어있다고 볼 수 있다. 

소스 코드

Union-find

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        p = [i for i in range(n)]
        def find(num):
            if p[num] != num:
                p[num] = find(p[num])
            return p[num]
        def union(a, b):
            p1 = find(a)
            p2 = find(b)
            if p1 != p2:
                p[p1] = p[p2]
        for u, v in edges:
            union(u, v)
        if find(source) == find(destination):
            return True
        return False

DFS

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        visited = [0] * n
        def dfs(n):
            if n == destination:
                return True
            if visited[n] == 1:
                return
            visited[n] = 1
            for nxt in g[n]:
                if dfs(nxt):
                    return True
            return False
        return dfs(source)