[BOJ/Platinum 2] 백준 10256 돌연변이(C++)

문제 링크

https://www.acmicpc.net/problem/10256

10256번: 돌연변이

 

문제

인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다.

이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA가 특정 문자열을 부분 문자열로 가진다면 그 질병에 걸릴 가능성이 높다는 것이다. 이러한 특정 문자열을 마커(marker)라 한다.

하지만 때때로 DNA 구조를 그대로 확인하는 것만으로는 질병과 관련된 마커를 확인할 수 없는 경우가 있다. 마커의 돌연변이 가능성 때문이다.

마커의 돌연변이는 아래와 같이 일어난다.

• 먼저, 마커를 세 부분으로 나눈다, 이때, 첫 부분과 세 번째 부분은 비어 있어도 된다.
• 두 번째 부분을 뒤집는다.

예를 들어 마커가 AGGT라면 아래와 같은 여섯 가지 경우가 가능하다.

GAGT, GGAT, TGGA, AGGT, ATGG, AGTG

어떤 사람의 DNA 구조와 마커가 주어졌을 때, DNA 내에 마커가 돌연변이의 형태를 포함하여 몇 번 출현하는지 세는 프로그램을 작성하라.

단, 마커의 출현 위치는 서로 겹쳐도 된다. 예를 들어 DNA 구조가 ATGGAT이며 마커가 AGGT라면 답은 3이 된다. ATGG, TGGA, GGAT가 한 번씩 출현하기 때문이다.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄엔 두 개의 정수 n과 m이 주어진다. 이는 각각 DNA 문자열의 길이와 마커의 길이이다. (1 ≤ n ≤ 1,000,000, 1 ≤ m ≤ 100) 두 번째 줄엔 DNA 구조가 주어진다. 마지막 줄엔 마커가 주어진다.

모든 DNA와 마커는 A,G,T,C로만 이루어진 문자열이다.

출력

각 테스트 케이스마다 주어진 DNA 구조에 마커와 그 돌연변이가 몇 번 출현하는지 하나의 정수로 출력한다.

만일 DNA 구조 내에 마커 또는 그 돌연변이가 한 번도 출현하지 않는다면 답은 0이 된다.

예제 입력 1

2
6 4
ATGGAT
AGGT
6 4
ATGGAT
AGCT

예제 출력 1

3
0

알고리즘 분류

• 트라이
• kmp

풀이

우선 마커를 트라이에 insert한다. 그리고 마커의 돌연변이가 될 수 있는 경우를 모두 탐색하면서 트라이에 insert한다.

그리고 DNA 문자열 내부에 마커와 돌연변이가 존재하는지 kmp 알고리즘을 통해 트라이에서 검색한다.

돌연변이는 마커 문자 사이사이를 기준점으로 간주하고, 첫 번째 기준점을 잡고 두 번째 기준점을 하나씩 M까지 늘려가면서 기준점 사이의 문자열만 역순으로 뒤집음으로써 찾는다. 마커의 최대 길이가 100이므로 경우의 수가 많지 않기 때문에 이중 for문으로 찾아준다.

메모리 제한이 적고, A, C, G, T 4가지의 문자만 입력받기 때문에 자식 노드를 저장하는 데 map이나 vector나 26만큼의 크기를 가지는 배열을 활용한다면 메모리 초과가 발생할 것이다.

따라서 A, C, G, T를 각각 0~3까지의 정수로 치환한 후 4만큼의 크기를 가지는 배열을 선언하여 자식 노드를 저장한다.

그리고 각 테스트케이스마다 kmp 알고리즘을 통해 마커 및 돌연변이의 개수를 구한 후 종료하기 전에 delete 함수를 사용하여 할당한 메모리를 해제해준다.

트라이 자체가 메모리를 많이 차지한다고 하고, 테스트 케이스가 얼마나 주어지는지도 모르기 때문에 최대한 적은 메모리를 할당할 수 있는 방법인 delete 함수를 생각했어야 했는데 그러지 못 했다. 아직 많이 부족한 것 같다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#define MAX 4
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int convert(char C) {
    if (C == 'A') {
        return 0;
    }
    else if (C == 'C') {
        return 1;
    }
    else if (C == 'G') {
        return 2;
    }
    else {
        return 3;
    }
}

struct TRIE {
    bool isEnd;
    TRIE* ChildTrie[MAX];
    TRIE* FailLink;

    TRIE() : isEnd(false), FailLink(nullptr) {
        fill(ChildTrie, ChildTrie + MAX, nullptr);
    }

    ~TRIE() {
        for (int i = 0; i < MAX; i++) {
            if (ChildTrie[i] != nullptr) {
                delete ChildTrie[i];
            }
        }
    }

    void insert_Pattern(string Pattern) {
        TRIE* NowTrie = this;
        for (int i = 0; i < Pattern.size(); i++) {
            int Now = convert(Pattern[i]);
            if (NowTrie->ChildTrie[Now] == nullptr) {
                NowTrie->ChildTrie[Now] = new TRIE;
            }

            NowTrie = NowTrie->ChildTrie[Now];
        }
        NowTrie->isEnd = true;
    }

    void find_FailLink() {
        TRIE* StartTrie = this;
        queue<TRIE*> Q;
        Q.push(StartTrie);

        while (!Q.empty()) {
            TRIE* NowTrie = Q.front();
            Q.pop();

            for (int i = 0; i < MAX; i++) {
                TRIE* NextTrie = NowTrie->ChildTrie[i];
                if (NextTrie == nullptr) {
                    continue;
                }

                if (NowTrie == StartTrie) {
                    NextTrie->FailLink = StartTrie;
                }
                else {
                    TRIE* PrevTrie = NowTrie->FailLink;
                    while ((PrevTrie != StartTrie) && (PrevTrie->ChildTrie[i] == nullptr)) {
                        PrevTrie = PrevTrie->FailLink;
                    };
                    if (PrevTrie->ChildTrie[i] != nullptr){
                        PrevTrie = PrevTrie->ChildTrie[i];
                    }
                    NextTrie->FailLink = PrevTrie;
                }
                if (NextTrie->FailLink->isEnd) {
                    NextTrie->isEnd = true;
                }
                Q.push(NextTrie);
            }
        };
    }
};

int T, N, M;
string DNA, Marker;

int kmp(string Now, TRIE* Root) {
    TRIE* NowTrie = Root;
    int Result = 0;
    for (int i = 0; i < Now.size(); i++) {
        while ((NowTrie != Root) && (NowTrie->ChildTrie[convert(Now[i])] == nullptr)) {
            NowTrie = NowTrie->FailLink;
        };

        if (NowTrie->ChildTrie[convert(Now[i])] != nullptr) {
            NowTrie = NowTrie->ChildTrie[convert(Now[i])];
        }
        
        if (NowTrie->isEnd) {
            Result++;
        }
    }

    return Result;
}

void find_Answer() {
    TRIE* Root = new TRIE();
    Root->insert_Pattern(Marker);
    for (int i = 0; i <= M; i++) {
        for (int j = (i + 2); j <= M; j++) {
            reverse(Marker.begin() + i, Marker.begin() + j);
            Root->insert_Pattern(Marker);
            reverse(Marker.begin() + i, Marker.begin() + j);
        }
    }
    Root->find_FailLink();
    cout << kmp(DNA, Root) << "\n";
    delete Root;
}

void input() {
    cin >> T;
    while (T--) {
        cin >> N >> M;
        cin >> DNA >> Marker;
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}