Leetcode - 1971. Find if Path Exists in Graph (Union Find 기초)

문제

edge가 주어질때, source -> destination 에대한 경로가 존재하면 true 아니면 false.

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

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.

https://leetcode.com/problems/find-if-path-exists-in-graph/

해결 아이디어

• Union Find
  • 두 노드가 같은 그룹에 속해있는지 판단할수 있는 알고리즘
  • 모든 노드의 최종 parent 를 찾아갈수 있는 배열을 생성하고 부모노드로 채움.
  • 주어지는 두 노드를 parent 배열을 통해 find()하고 최종 root 노드가 같은 노드이면 같은 그룹에 속한 노드이고, 다르면 서로다른 그룹에 속한 노드.

풀이

class Solution {
public:
    vector<int> parent;
    int find(int n) {
        if (parent[n] == n) // 부모가 자기자신이면 그게 최종 root노드
            return n;
        return find(parent[n]); 
    }
    void do_union(int a, int b) {
        int roota = find(a);
        int rootb = find(b);
        parent[roota] = rootb; // 결국 a의 root노드의 부모노드는 b의 root노드가 됨. 연결됨.
    }
    bool validPath(int n, vector<vector<int>>& edges, int src, int dst) {
        parent = vector<int>(n, 0);
        for (int i = 0; i < n; i++)
            parent[i] = i;
        for (auto it: edges)
            do_union(it[0], it[1]);
        return find(src) == find(dst); // 같은 그룹이라면 반드시 같은 노드를 가리키게됨.
    }
};