C++로 유전자 서열의 전체 돌연변이 그룹 개수 찾기

모든 요소의 길이가 같고 문자 'A', 'C', 'G', 'T'로만 구성된 문자열 리스트 genes가 있다고 가정해 보겠습니다. 이때 다음과 같은 규칙이 적용됩니다.

두 문자열 s1과 s2가 단 한 글자만 다를 경우, 두 문자열은 같은 돌연변이 그룹에 속합니다.
s1과 s2가 같은 그룹에 있고, s2와 s3가 같은 그룹에 있다면 s1과 s3 역시 같은 그룹에 속합니다(추이성).

우리가 구해야 하는 값은 이 규칙들로부터 만들어질 수 있는 돌연변이 그룹의 총 개수입니다.

예를 들어 입력이 genes = ["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"]라면 출력은 2가 됩니다. 돌연변이 그룹이 ["ACGT", "ACGC", "ACTT"]와 ["TTTT", "TGTT"] 두 개로 나뉘기 때문입니다.

문제 해결 접근 방법

이 문제는 유니온-파인드(Union-Find), 즉 서로소 집합(Disjoint Set) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 한 글자만 다른 문자열들을 하나의 집합으로 묶어 나가면, 최종적으로 남는 집합의 개수가 곧 돌연변이 그룹의 개수가 됩니다.

알고리즘 단계

부모 노드를 저장하는 맵 parent를 정의합니다.
getPar() 함수를 정의합니다. 인자 a에 대해 parent[a]가 a 자신과 같다면 a를 반환하고, 그렇지 않으면 경로 압축을 통해 재귀적으로 루트 부모를 찾아 갱신한 뒤 반환합니다.
unite() 함수를 정의합니다. a와 b의 루트 부모 parA, parB를 구하고, 서로 다르면 parent[parA]를 parB로 설정하여 두 집합을 합친 후 true를 반환합니다. 이미 같은 집합이라면 false를 반환합니다.
ok() 함수를 정의합니다. 두 문자열을 비교하여 다른 문자의 개수(cnt)를 세고, cnt가 정확히 1일 때만 true를 반환합니다.
메인 로직은 다음과 같이 진행됩니다.
- 배열 v를 정렬하고, v의 모든 원소를 담은 집합 s를 만듭니다.
- ret을 v의 크기로 초기화합니다. 처음에는 모든 문자열이 각각 별개의 그룹이라고 가정하는 것입니다.
- v의 각 원소 it에 대해 parent[it]를 자기 자신으로 초기화합니다.
- it의 각 위치 j에 대해, 해당 위치의 문자를 'A', 'C', 'G', 'T' 중 다른 문자로 하나씩 바꿔본 임시 문자열 temp를 만듭니다.
- temp가 집합 s에 존재한다면 unite(temp, it)를 호출해 두 문자열을 같은 그룹으로 합치고, 합치기에 성공했다면(새로운 병합이 일어났다면) ret을 1 감소시킵니다.
최종적으로 ret을 반환합니다. 이 값이 곧 돌연변이 그룹의 총 개수입니다.

핵심 아이디어는 가능한 모든 문자열 쌍을 직접 비교하는 대신, 각 문자열의 한 위치를 다른 염기로 바꿔본 후보가 실제로 목록에 존재하는지만 확인하면 된다는 점입니다. 이를 통해 불필요한 비교를 크게 줄일 수 있습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map <string, string> parent;
   string getPar(string& a){
      if(parent[a] == a)
         return a;
      return parent[a] = getPar(parent[a]);
   }
   bool unite(string& a, string& b){
      string parA = getPar(a);
      string parB = getPar(b);
      if(parA != parB){
         parent[parA] = parB;
         return true;
      }
      return false;
   }
   bool ok(string &a, string& b){
      int cnt = 0;
      for(int i = 0; i < a.size(); i++){
         cnt += a[i] != b[i];
      }
      return cnt == 1;
   }
   int solve(vector<string> v) {
      sort(v.begin(), v.end());
      set <string> s(v.begin(), v.end());

      int ret = v.size();
      for(auto& it : v){
         parent[it]= it;
      }
      for(auto& it : v){
         for(int j = 0; j < it.size(); j++){
            string temp = it;
            for(char x : {'A', 'C', 'G', 'T'}){
               if(x != it[j]){
                  temp[j] = x;
                  if(s.count(temp)){
                     if(unite(temp, it)) ret--;
                  }
               }
            }
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
   Solution ob;
   cout << ob.solve(v);
}

입력

{"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}