C++로 구현하는 문장 유사성 판별 II — 유니온-파인드(Union-Find) 알고리즘 완전 정복

문제 소개

두 배열 words1과 words2가 주어지며, 각각 하나의 문장으로 간주합니다. 여기에 유사한 단어 쌍 목록 pairs가 함께 제공되었을 때, 두 문장이 서로 유사한지 판별하는 것이 이 문제의 핵심입니다.

예를 들어 words1 = ["great", "acting", "skills"], words2 = ["fine", "drama", "talent"]이고, 유사 단어 쌍이 [["great", "good"], ["fine", "good"], ["acting", "drama"], ["skills", "talent"]]라고 한다면, 두 문장은 유사한 것으로 판정됩니다.

유사성의 세 가지 성질

1. 추이성(Transitivity): "great"과 "good"이 유사하고, "fine"과 "good"도 유사하다면, "great"과 "fine" 역시 유사합니다.

2. 대칭성(Symmetry): "great"과 "fine"이 유사하다는 것은 "fine"과 "great"이 유사하다는 것과 동일한 의미입니다.

3. 반사성(Reflexivity): 모든 단어는 항상 자기 자신과 유사합니다.

마지막으로, 두 문장이 유사하려면 반드시 단어의 개수가 같아야 한다는 전제 조건이 있습니다.

해결 접근 방법

이 문제는 유니온-파인드(Union-Find, 서로소 집합) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 각 단어에 고유 번호를 부여하고, 유사 쌍끼리 하나의 집합으로 묶은 뒤, 위치가 대응되는 단어들이 같은 집합에 속하는지만 확인하면 됩니다.

알고리즘 단계

부모 노드를 저장할 맵 parent와 단어-번호 매핑용 맵 idx를 정의합니다.
getParent(x) 함수를 정의합니다.
- x가 parent에 없으면 x를 그대로 반환합니다.
- 그렇지 않으면 경로 압축(path compression)을 적용하여 parent[x] := getParent(parent[x])로 갱신한 뒤 반환합니다.
unionn(a, b) 함수를 정의합니다.
- parentA := getParent(idx[a]), parentB := getParent(idx[b])를 구합니다.
- 두 값이 같으면 이미 같은 집합이므로 그대로 종료합니다.
- 다르면 parent[parentA] := parentB로 두 집합을 병합합니다.
메인 메서드에서 다음 과정을 수행합니다.
- words1과 words2의 크기가 다르면 false를 반환합니다.
- n := words1의 크기, counter := 1로 초기화합니다.
- words1의 모든 단어를 순회하며 idx에 없는 단어에는 새 번호를 부여합니다.
- words2의 모든 단어에 대해서도 동일하게 번호를 부여합니다.
- pairs의 각 쌍(u, v)에 대해 번호가 없으면 부여한 후 unionn(u, v)으로 병합합니다.
- 각 위치 i마다 u := words1[i], v := words2[i]를 비교합니다.
  - u와 v가 같으면 다음 반복으로 건너뜁니다.
  - getParent(idx[u]) != getParent(idx[v])이면 false를 반환합니다.
- 모든 검사를 통과하면 true를 반환합니다.

C++ 구현 예제

아래 구현 코드를 통해 더 깊이 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    unordered_map<int, int> parent;
    unordered_map<string, int> idx;
    int getParent(int x){
        if (!parent.count(x))
            return x;
        return parent[x] = getParent(parent[x]);
    }
    void unionn(string a, string b){
        int parentA = getParent(idx[a]);
        int parentB = getParent(idx[b]);
        if (parentA == parentB)
            return;
        parent[parentA] = parentB;
    }
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string> >& pairs){
        if (words1.size() != words2.size())
            return false;
        int n = words1.size();
        int counter = 1;
        for (int i = 0; i < n; i++) {
            if (!idx.count(words1[i])) {
                idx[words1[i]] = counter++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!idx.count(words2[i])) {
                idx[words2[i]] = counter++;
            }
        }
        for (int i = 0; i < pairs.size(); i++) {
            string u = pairs[i][0];
            string v = pairs[i][1];
            if (!idx.count(u)) {
                idx[u] = counter++;
            }
            if (!idx.count(v)) {
                idx[v] = counter++;
            }
            unionn(u, v);
        }
        for (int i = 0; i < n; i++) {
            string u = words1[i];
            string v = words2[i];
            if (u == v)
                continue;
            if (getParent(idx[u]) != getParent(idx[v]))
                return false;
        }
        return true;
    }
};
main(){
    Solution ob;
    vector<string> v = { "great", "acting", "skills" }, v1 = { "fine", "drama", "talent" };
    vector<vector<string> > v2 = { { "great", "good" }, { "fine", "good" }, { "drama", "acting" }, { "skills", "talent" } };
    cout << (ob.areSentencesSimilarTwo(v, v1, v2));
}

입력

{"great","acting","skills"}, {"fine","drama","talent"},
{{"great","good"},{"fine","good"},{"drama","acting"},{"skills","talent"}}

출력

복잡도 분석

경로 압축이 적용된 유니온-파인드 연산은 평균적으로 거의 상수 시간에 수행됩니다. 따라서 고유 단어 수를 N, 유사 쌍의 개수를 P라고 할 때, 전체 시간 복잡도는 O((N + P) · α(N + P))(α는 아커만 역함수로 사실상 상수)이며, 공간 복잡도는 O(N + P)입니다. 덕분에 입력 크기가 커져도 안정적인 성능을 기대할 수 있습니다.