Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 해결하는 최소 유전자 돌연변이 문제: BFS 알고리즘 접근법

문제 소개

유전자 문자열(gene string)은 길이가 8인 문자열로, A, C, G, T 네 가지 문자로만 구성됩니다. 여기서 하나의 '돌연변이(mutation)'란 유전자 문자열에서 단 한 글자를 다른 문자로 바꾸는 것을 의미합니다. 예를 들어 "AACCGGTT"에서 마지막 문자를 바꾼 "AACCGGTA"는 1회 돌연변이에 해당합니다.

또한 유효한 유전자 변이들이 담긴 유전자 뱅크(bank)가 주어집니다. 어떤 유전자가 유효하려면 반드시 이 뱅크 안에 존재해야 합니다.

세 가지 입력 — start(시작 유전자), end(목표 유전자), bank(유전자 뱅크) — 이 주어졌을 때, 우리의 목표는 start에서 end까지 도달하는 데 필요한 최소 돌연변이 횟수를 구하는 것입니다. 만약 변환이 불가능하다면 -1을 반환해야 합니다.

예시

입력이 다음과 같다고 가정해 보겠습니다.

  • start = "AACCGGTT"
  • end = "AAACGGTA"
  • bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

이 경우 출력은 2입니다. "AACCGGTT" → "AACCGGTA" → "AAACGGTA" 순서로 두 번의 변이를 거치면 되기 때문입니다.

접근 방법: 와일드카드 패턴 + BFS

이 문제의 핵심 아이디어는 각 유전자를 그래프의 노드로 보고, 한 글자만 다른 유전자들을 간선으로 연결한 뒤 너비 우선 탐색(BFS)으로 최단 경로를 찾는 것입니다.

두 유전자를 일일이 비교하는 대신 와일드카드(*) 패턴을 활용하면 더 효율적입니다. 예를 들어 "AACCGGTT"는 "*ACCGGTT", "A*CCGGTT", ..., "AACCGGT*"처럼 8개의 패턴으로 표현할 수 있습니다. 동일한 패턴을 공유하는 두 유전자는 정확히 한 글자만 다르다는 뜻입니다.

알고리즘 단계

  1. putStar() 함수 정의: 문자열 s를 받아 각 위치의 문자를 '*'로 대체한 패턴 배열 ret을 생성해 반환합니다.
  2. 그래프 생성: 뱅크의 모든 유전자에 대해 putStar()를 호출하고, 각 패턴을 키로 삼아 해당 유전자를 맵(graph)의 인접 리스트에 추가합니다.
  3. BFS 초기화: 큐 q에 start를 넣고, 방문 집합(visited)에도 start를 추가합니다.
  4. 레벨별 탐색: 큐가 빌 때까지 레벨(lvl)을 1부터 증가시키며, 현재 레벨의 노드 수(sz)만큼 반복합니다.
    • 큐에서 노드를 꺼내 putStar()로 패턴 배열 out을 얻습니다.
    • 각 패턴 u에 연결된 모든 유전자 v를 확인합니다.
    • v를 이미 방문했다면 건너뜁니다.
    • v가 end와 같다면 현재 레벨 lvl을 반환합니다.
    • 그렇지 않으면 v를 방문 처리하고 큐에 추가합니다.
  5. 실패 처리: 큐가 비었는데도 end에 도달하지 못했다면 -1을 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector<string> putStar(string s){
        vector<string> ret;
        for(int i = 0; i < s.size(); i++){
            string temp = s.substr(0, i) + "*" + s.substr(i + 1);
            ret.push_back(temp);
        }
        return ret;
    }
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_map<string, vector<string>> graph;
        for(int i = 0; i < bank.size(); i++){
            string s = bank[i];
            vector<string> out = putStar(bank[i]);
            for(int j = 0; j < out.size(); j++){
                graph[out[j]].push_back(s);
            }
        }
        queue<string> q;
        q.push(start);
        set<string> visited;
        visited.insert(start);
        for(int lvl = 1; !q.empty(); lvl++){
            int sz = q.size();
            while(sz--){
                string node = q.front();
                q.pop();
                vector<string> out = putStar(node);
                for(int i = 0; i < out.size(); i++){
                    string u = out[i];
                    for(int j = 0; j < graph[u].size(); j++){
                        string v = graph[u][j];
                        if(visited.count(v)) continue;
                        if(v == end) return lvl;
                        visited.insert(v);
                        q.push(v);
                    }
                }
            }
        }
        return -1;
    }
};
main(){
    Solution ob;
    vector<string> v = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
    cout << (ob.minMutation("AACCGGTT", "AAACGGTA", v));
}

입력 및 출력

입력

"AACCGGTT", "AAACGGTA", {"AACCGGTA", "AACCGCTA", "AAACGGTA"}

출력

2

복잡도 분석

  • 시간 복잡도: O(N × L²) — N은 뱅크에 있는 유전자의 개수, L은 유전자 길이(8)입니다. 그래프 생성에 O(N × L), BFS 과정에서 각 노드마다 패턴 생성과 조회가 발생합니다. L이 상수이므로 실질적으로 O(N)에 가깝습니다.
  • 공간 복잡도: O(N × L) — 그래프, 큐, 방문 집합에 유전자와 패턴 정보가 저장됩니다.