[BOJ] 백준 10256. 돌연변이 (Platinum III)

스코페에서 아호코라식 알고리즘이 출제가 돼서 언젠가 공부를 해야겠다 해야겠다 하고 미루다가 오늘에서야 공부하고 풀게 된 문제이다.

www.acmicpc.net/problem/10256

10256번: 돌연변이

난이도 기여 의견

아호코라식 말고 간단한 풀이가 더 있는 듯 한데,

일단 난 9250번 문제(아호코라식의 정석 개념예제 문제)보다 어려운 듯 하여 P2에 투표하였다.

(아호코라 식이 아니고 aho-corasick 이었어..? ㅋㅋㅋㅋ)

 

이 아호코라식이라는 거... 정말 엄청 어렵다.

일단 장점은 KMP나 트라이 같은 경우는 한 문자열에 매칭하는 데에 특화돼있다는 점인데,

이 아호코라식은 KMP + Trie + BFS를 짬뽕해버려서 여러 문자열을 매칭할 수 있다! (대신 그만큼 겁나게 어렵다)

 

 

아호코라식을 공부하기 위해 구글링한 결과 역시나 고급알고리즘 포스팅의 대명사, kks227님 블로그 포스팅이 최상단에 떠서 그 블로그로 공부하였고,

9250번 예제 문제는 justicehui님 블로그, kks227님 블로그를 참고하여 공부하였다. 두 분의 풀이가 거의 비슷하다. justicehui님께서는 깔끔하게 함수화한 풀이, kks227님은 string 헤더파일이 필요없는 char 풀이로 이용하셨는데, 

아무래도 두 분의 풀이가 거의 비슷하다보니 내 풀이 또한 kks227님과 justicehui님의 블로그와 비슷하게 됐다.

 

(솔직히 특정 알고리즘의 예제문제같은 경우 솔브드 티어 레이팅에 반영되면 너무 레이팅 뻥튀기되는 듯해서 싫다.)

아무튼 이렇게 아호코라식의 슈도코드를 대략적으로 세우고 9250번 AC로 검증했으므로, 응용문제를 풀어보기로 했다.

그 응용문제가 바로 지금 포스팅하려는 문제이다.

---

의식의 흐름 및 해설

솔직히 의식의 흐름이고 뭐고, 이번 문제는 아호코라식을 연습하려고 들어간 예제 문제라 알고리즘이 스포당한 상태에서 풀었다. 그래서 뭐... 딱히 적을게 없다. 솔직히 ps는 알고리즘 알아내면서 퍼즐처럼 푸는 재미인데 말이지..ㅋㅋ

 

일단 이 문제가 아호코라식인 이유는 마커와 마커의 돌연변이들이 DNA에 매칭되는지 확인해야하기 때문이다. 

이 문제를 만약 KMP로 풀게 된다면 마커의 경우의 수가 총 M^2까지 나올 수 있으므로 O(NM^2)이므로 시간초과를 겪게 된다. 내가 스코페 2차대회 4번을 kmp로 풀었던 기억이 나는구만...

 

따라서 일대다 문자열매칭이 가능한 아호코라식을 떠올려야 하며, 이 때 시간복잡도는 O(N+M^2)이므로 시간초과에 걸리지 않는다. 다만, 트라이 특성 상 메모리를 굉장히 많이 차지하고, 여러 테스트케이스를 거치는 문제이므로 실제 시간은 위 시간복잡도 계산보다 훨씬 많이 걸리게 된다. 

 

따라서 메모리를 최대한 아끼는 것이 시간초과를 막을 수 있는 관건. 

그러므로 어차피 AGCT만 존재하는거, 알파벳 모든 경우인 26개를 동적할당하기보단, A, C, G, T를 각각 '0', '1', '2', '3'으로 바꿔 4개만 동적할당할 수 있게 해주자.

---

시행착오 및 결과

제출하기 전에 애먹었던 점은, reverse(marker.begin()+i, marker.begin()+j) 이 부분인데, j<=M 까지 진행해야 M-1까지 뒤집히는데, j<M으로 해서 M-2까지의 범위만 뒤집혀서 고생했었다. (끝부분 idx 제외하고 뒤집잖아 내 일병 육군 빡빡이 빡대가리야... 기억하자 이제 ㅠㅠㅠ)

 

맨 처음에 '틀렸습니다' 는 마커의 돌연변이들만 집어넣고, 막상 마커 자기 자신은 넣지 않아서 발생한 결과이다. ㅋㅋㅋㅋㅋㅋㅋ 레전드

 

시간초과는 A, C, G, T 이 네가지 경우 뿐만 아니라 알파벳 모든 경우의 수 (26가지)를 모두 동적할당한 경우 발생한다. 메모리가 너무 커서 시간 또한 오래걸리는 셈이다.

 

세번째의 틀렸습니다는... 그냥 개뻘짓해서 트라이 좀 바꾸다가 오히려 틀려버린 케이스이다.

---

테스트케이스

2
6 4
ATGGAT
AGGT
6 4
ATGGAT
AGCT
ans:
3
0


2
6 4
ATGGAT
AGCT
8 2
GTACCTAC
CT
ans: 
0
1

2
8 2
GTACCTAC
CT
6 4
ATGGAT
AGCT
ans:
1
0

두번째 세번째 같은 경우는 16%에서 WA를 받을 경우 유용할 것이다.

만약, 33%에서 시간초과가 뜬다면... 동적할당을 너무 많이 했을 확률이 높다. (26개의 알파벳 모두 동적할당한경우)

---

코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, M;
struct Trie {
	Trie* next[4];
	Trie* fail;
	int output;
	Trie() : output(0), fail(nullptr) {
		fill(next, next + 4, nullptr);
	}
	~Trie() {
		for (int i = 0; i < 4; i++) {
			if (next[i])
				delete next[i];
		}
	}
	void insert(string& s, int idx) {
		if (idx >= s.length()) {
			output = 1;
			return;
		}
		int x = s[idx] - '0';
		if (!next[x]) {
			next[x] = new Trie();
		}
		next[x]->insert(s, idx + 1);
	}
};
void fail(Trie* root) {
	queue<Trie*> q;
	root->fail = root;
	q.push(root);
	while (!q.empty()) {
		Trie* cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			Trie* nxt = cur->next[i];
			if (!nxt)
				continue;
			if (root == cur)
				nxt->fail = root;
			else {
				Trie* tmp = cur->fail;
				while (tmp != root && !tmp->next[i])
					tmp = tmp->fail;
				if (tmp->next[i])
					tmp = tmp->next[i];
				nxt->fail = tmp;
			}
			nxt->output += nxt->fail->output;
			q.push(nxt);
		}
	}
}
int solve(string s, Trie* root) {
	int ret = 0;
	Trie* cur = root;
	for (int i = 0; i < s.length(); i++) {
		int nxt = s[i] - '0';
		while (cur != root && !cur->next[nxt])
			cur = cur->fail;
		if (cur->next[nxt])
			cur = cur->next[nxt];
		ret += cur->output;
	}
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	
	int t;
	cin >> t;
	while (t--) {
		cin >> N >> M;
		string s, m;
		cin >> s >> m;
		Trie* root = new Trie();
		for (int i = 0; i < N; i++) {
			if (s[i] == 'A')
				s[i] = '0';
			else if (s[i] == 'C')
				s[i] = '1';
			else if (s[i] == 'G')
				s[i] = '2';
			else
				s[i] = '3';
		}
		for (int i = 0; i < M; i++) {
			if (m[i] == 'A')
				m[i] = '0';
			else if (m[i] == 'C')
				m[i] = '1';
			else if (m[i] == 'G')
				m[i] = '2';
			else
				m[i] = '3';
		}
		root->insert(m, 0);
		for (int i = 0; i <= M; i++) {
			for (int j = i + 2; j <= M; j++) {
				reverse(m.begin() + i, m.begin() + j);
				root->insert(m, 0);
				reverse(m.begin() + i, m.begin() + j);
			}
		}
		fail(root);
		cout << solve(s, root) << "\n";
		delete root;
	}
}

---

이 문제는 우리학교에서 푼 사람이 없었다. 

따라서 이 문제를 풀음으로써 랭킹 기여에 조금이나마 도움이 된 셈이다.

아호코라식 연습도 하고 랭킹 기여도 하고 일석이조이다.

 

내 솔브드 레이팅은 좀 안올랐으면 좋겠는데, 이 문제로 또 다시 뻥튀기가 되어버렸다. 아직 내 티어가 P1이라기엔 자력으로 풀 수 있는 P1 문제가 많지 않은데.. P4~P3만 돼도 버거워한다.

 

사실 아직 두문제만 풀었으므로 아호코라식이 크게 손에 익지 않는다.

실패함수 원리와 solve 함수 원리를 어렴풋이 이해만 했다는 느낌만 들어서 좀 더 많은 연습이 필요할 듯하다.

마치 유니온파인드, scc문제처럼 말이다. (scc 알고리즘도 시간이 지나면 지날수록 여러 dfs, graph cycle 문제를 겪으면서 이해도가 높아졌다. cycle에서 좀 더 부분집합으로 들어가면 scc인 것처럼 말이다.)

 

결론: 문자열, 열심히 더 연습하자. 오늘은 감을 잡았다 생각하자.