99클럽 코테 스터디 25일차 TIL - 1971 Find if Path Exists in Graph

1971. Find if Path Exists in Graph / c++ / Easy / 26분

문제 및 코드

#include <iostream>
using namespace std;

vector<int> parent;

int Find(int num)
{
    if (parent[num] == num)
    {
        return num;
    }

    return parent[num] = Find(parent[num]);
}

void Union(int a, int b)
{
    int parentA = Find(a);
    int parentB = Find(b);

    if (parentA ==parentB) return;

    parent[parentB] = parentA;
}


class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        parent = vector<int>(n, 0);

        for (int i = 0; i < n; ++i)
        {
            parent[i] = i;
        }

        for (int i = 0; i < edges.size(); ++i)
        {
            Union(edges[i][0], edges[i][1]);
        }

        return Find(source) == Find(destination);
    }
};

접근 방식

유니온파인드

1. 양방향 그래프에서 두 정점 사이의 경로가 존재하는지를 반환하는 문제였다.
2. 유니온파인드(디스조인트셋/서로소 집합)을 사용하면 두 정점의 부모가 같을 경우 두 정점의 경로가 존재함을 알 수 있다.

생각해 볼 점

1. 99클럽의 챌린저 문제 치고는 너무 쉬웠다. (리트 코드 난이도 조차도 easy)
2. 아마 source 정점에서 BFS나 DFS등을 써서 destination 정점까지 도착할 수 있는지를 파악할 수도 있을 것 같다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL