[LeetCode] 2092. Find All People With Secret

 

https://leetcode.com/problems/find-all-people-with-secret/description/?envType=daily-question&envId=2025-12-19

LeetCode - 2092. Find All People With Secret

문제 유형: 유니온-파인드

문제 난이도: Hard

 

문제

You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [xi, yi, timei] indicates that person xi and person yi have a meeting at timei. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person xi has the secret at timei, then they will share the secret with person yi, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

 

n명의 사람이 0~n-1번호로 부여됩니다. 

meetings[i] = [x, y, time]으로 구성되는데, x와 y가 time에 회의에 참여함을 의미합니다. 

회의에 참여하면 비밀을 공유합니다.

같은 시간에 여러 미팅에 참여할 수 있고, 미팅은 동시적으로 이뤄집니다.

 

0번 사람은 비밀을 알고 있습니다.

그리고 시간 0에 0번사람이 firstPerson에게 비밀을 전파합니다.

 

비밀을 아는 사람들을 모두 구하시오. 순서는 상관 없습니다.

 

풀이

유니온 파인드를 이용하여 사람들을 묶으면 된다.

그러나, 비밀이 없는 사람들만 참여하면, 그 회의는 의미가 없어진다.

그래서, 해당 유니온 파인드를 롤백할 필요가 있다.

 

아래 구현에서는 유니온 파인드의 로직으로, 비밀을 아는 사람들은 공통 루트가 0으로 향하게 하였다.

즉, 이번 같은 시간동안에 같이 한사람들을 유니온 파인드에 포함했다가, 그 그룹의 루트가 0을 향하지 않으면 다시 롤백하면 된다.

 

최종적으로 루트를 0으로 하는 번호들을 정답에 넣는다.

 

코드

C++

class Solution {
public:
    int find(vector<int>& parent, int x) {
        if(parent[x] == x) return x;
        return parent[x] = find(parent, parent[x]);
    }
    void unite(vector<int>& parent, int x, int y) {
        x = find(parent, x);
        y = find(parent, y);

        if(x == y) return;
        if(x < y) {
            parent[y] = x;
        } else {
            parent[x] = y;
        }
    }
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        int m = meetings.size();
        sort(meetings.begin(), meetings.end(), [](const auto &a, const auto &b){
            return a[2] < b[2];
        });

        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        unite(parent, 0, firstPerson);

        for(int l = 0, r = 0; l < meetings.size();) {
            for(; r < meetings.size() && meetings[l][2] == meetings[r][2]; ++r) {
                unite(parent, meetings[r][0], meetings[r][1]);
            }

            // if fail, rollback
            for(; l < r; ++l) {
                if(find(parent, meetings[l][0]) != 0) parent[meetings[l][0]] = meetings[l][0];
                if(find(parent, meetings[l][1]) != 0) parent[meetings[l][1]] = meetings[l][1];
            }
        }

        vector<int> ans;
        for(int i = 0; i < n; i++) {
            if(find(parent, i) == 0) ans.emplace_back(i);
        }

        return ans;
    }
};