Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

C++ 유니온 파인드(Union-Find)로 푸는 '모두가 친구가 되는 가장 빠른 시간' 문제

소셜 그룹에 N명의 사람이 있으며, 각 사람은 0부터 N-1까지의 고유한 정수 ID를 가지고 있다고 가정해 봅시다. 우리에게는 로그 목록이 주어지는데, 각 로그 logs[i] = [time, id_A, id_B]는 음이 아닌 정수 타임스탬프와 서로 다른 두 사람의 ID를 담고 있습니다. 각 로그는 두 사람이 친구가 된 시점을 나타내며, A가 B의 친구라면 B도 A의 친구입니다.

여기서 'A가 B와 아는 사이'라는 것은 A가 B의 직접적인 친구이거나, A가 B와 아는 사이인 누군가의 친구인 경우를 의미합니다. 즉, 친구 관계는 전이적으로 연결됩니다. 우리가 구해야 할 것은 모든 사람이 서로 아는 사이가 되는 가장 이른 시간이며, 그런 시간이 존재하지 않으면 -1을 반환하면 됩니다.

문제 예시

입력이 다음과 같다고 해봅시다.

[[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6

이때 출력은 20190301입니다. 그 과정을 단계별로 살펴보면 다음과 같습니다.

  • 첫 번째 이벤트(타임스탬프 20190101): 0번과 1번이 친구가 되어 친구 그룹은 [0,1], [2], [3], [4], [5]가 됩니다.
  • 두 번째 이벤트(타임스탬프 20190104): 3번과 4번이 친구가 되어 그룹은 [0,1], [2], [3,4], [5]가 됩니다.
  • 세 번째 이벤트(타임스탬프 20190107): 2번과 3번이 친구가 되어 그룹은 [0,1], [2,3,4], [5]가 됩니다.
  • 네 번째 이벤트(타임스탬프 20190211): 1번과 5번이 친구가 되어 그룹은 [0,1,5], [2,3,4]가 됩니다.
  • 다섯 번째 이벤트(타임스탬프 20190224): 2번과 4번은 이미 친구이므로 변화가 없습니다.
  • 여섯 번째 이벤트(타임스탬프 20190301): 0번과 3번이 친구가 되면서 모든 사람이 하나의 그룹으로 연결됩니다.

해결 접근 방식

이 문제는 대표적인 유니온 파인드(Union-Find, 서로소 집합) 알고리즘으로 해결할 수 있습니다. 로그를 시간순으로 정렬한 뒤, 친구 관계를 하나씩 병합하면서 그룹의 크기가 N에 도달하는 순간의 타임스탬프를 반환하면 됩니다.

find() 메서드

  • x를 인자로 받아 x의 루트 부모를 찾습니다.
  • parents[x]가 -1이면 x가 루트이므로 x를 반환합니다.
  • 그렇지 않으면 parents[x] := find(parents[x])로 경로 압축을 수행한 후 parents[x]를 반환합니다.

메인 메서드

  • 크기 N의 parents 배열(-1로 초기화)과 rank 배열(1로 초기화)을 정의합니다.
  • 로그를 오름차순으로 정렬합니다.
  • 각 로그 요소 i에 대해 다음을 수행합니다.
    • i[1]과 i[2]에 대해 union 연산을 수행합니다.
    • find(i[1])과 find(i[2])로 각각의 루트를 확인합니다.
    • rank 배열에 N이 존재하면(모든 사람이 한 그룹에 속하면) i[0], 즉 해당 타임스탬프를 반환합니다.
  • 모든 로그를 처리한 후에도 그룹이 통합되지 않았다면 -1을 반환합니다.

C++ 구현 예제

아래 구현에서는 parents 배열에 음수 값을 저장하여 루트 여부와 그룹 크기를 동시에 관리하는 최적화 기법을 사용했습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int earliestAcq(vector<vector<int>>& logs, int N) {
      vector<int> ds (N, -1);
      sort(begin(logs), end(logs));
      for(vector<int> &k : logs) {
         if(un(k[1], k[2], ds) == N) return k[0];
      }
      return -1;
   }
   int un(int u, int v, vector<int> & ds) {
      u = find(u, ds);
      v = find(v, ds);
      if(u != v) {
         ds[v] += ds[u];
         ds[u] = v;
      }
      return -ds[v];
   }
   int find(int u, vector<int> & ds) {
      return ds[u] < 0? u : ds[u] = find(ds[u], ds);
   }
};
main(){
   vector<vector<int>> v = {
      {20190101,0,1},{20190104,3,4},{20190107,2,3},{20190211,1,5},
      {20190224,2,4},{20190301,0,3},{20190312,1,2},{20190322,4,5}
   };
   Solution ob;
   cout <<ob.earliestAcq(v, 6);
}

입력

[[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]]
6

출력

20190301