[BOJ] 백준 10256번 돌연변이 (Java)

#10256 돌연변이

난이도 : 플레 2

유형 : 문자열  / 트라이 /  아호-코라식

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이 된다.

 

문제 풀이  

최대 100개의 길이로 이루어진 마커 구조로 주어질 때 구할 수 있는 변이 구조의 갯수는 대략 100^2개 정도 된다. 그러면 1만개의 문자열을 100만 길이가 되는 DNA에 하나씩 매칭을 하면 시간초과가 발생한다. 그래서 다중 문자열 탐색 아호-코라식 알고리즘을 사용해야한다.

• p 패턴 수 : 10,000개
• s 모든 패턴들의 길이 합 : 1,000,000 
• n 크기 : 1,000,000

💡 아호-코라식(Aho-Corasick) 알고리즘에 대한 설명은 여기를 참고해주세요.

 

아호-코라식 알고리즘을 사용하면 O(n+s+p) 시간복잡도로 해결이 가능하다. 문자열 집합을 트리 구조로 저장하는 트라이 자료구조를 사용해서 실패 링크와 출력 문자열 목록을 생성한 다음 KMP 알고리즘과 같은 방식으로 매칭 문자열을 탐색해주면 된다.

 

예제에 나온 변이에 대한 트라이 자료구조는 다음과 같다. 아호-코라식을 사용하기 위해서는 해당 자료구조에 실패 링크와 출력 문자열 목록을 추가해주면 된다.

 

트라이 자료구조

 

 

추가로, 변이를 만드는 시간복잡도 O(m^2)가 추가로 소요된다. 변이를 만드는 방법은 문자열 길이에서 연속된 모든 부분 문자열을 뒤집어주면 된다. 로직은 다음과 같다.

for (int i = 0; i < m; i++) {
	for (int j = i + 1; j < m; j++) {
	   String 변이 = reverseString(pattern,i,j+1);
	}
}
            
public static String reverseString(String tmp, int s, int e) {
	StringBuilder sb = new StringBuilder();
	sb.append(tmp.substring(0, s));
	sb.append(new StringBuilder(tmp.substring(s, e)).reverse());
	sb.append(tmp.substring(e, tmp.length()));
	return sb.toString();
}

 

설계

1. 트라이(Trie) 자료구조를 구현한다. 
   1. 기존 트라이 자료구조에서 실패링크를 추가한다.
   2. 실패 링크를 계산하는 로직을 추가한다.
   3. 탐색 문자열(word)와 매칭시키는 KMP 알고리즘을 구현한다.
      1. 몇 글자나 대응되었는지를 나타내는 matched 변수 → 현재 상태를 나타내는 trieNode
      2. 부분 일치 테이블 참조 대신 →  실패 링크를 참조
2. 주어지는 marker에 대한 모든 변이를 구한다음 을 트라이 자료구조에 저장한다.  trie.insert("변이");
3. 실패함수를 계산해준다. computeFailFunc()
4. 판별해야 하는 문자열이 매칭되는 횟수를 출력해준다.  ahoCorasick(String word)

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	static Map<Character, Integer> data = new HashMap<>();
	static {
		data.put('A', 0);
		data.put('G', 1);
		data.put('T', 2);
		data.put('C', 3);
	}
	
	static class TrieNode{
		Map<Integer, TrieNode> child = new HashMap<>();
		boolean output;
		TrieNode fail;
		
		public TrieNode() {}
		
		public void insert(String word) {
			TrieNode curNode = this;
			for(int i=0; i<word.length(); i++) {
				int key = data.get(word.charAt(i));
				curNode = curNode.child
						.computeIfAbsent(key, c -> new TrieNode());
			}
			curNode.output = true;
		}
		
		public void computeFailFunc() {
			Queue<TrieNode> q = new LinkedList<>();
			this.fail = this;
			q.add(this);
			
			while(!q.isEmpty()) {
				TrieNode curNode = q.poll();
				
				for(char c : data.keySet()) {
					int key = data.get(c);
					TrieNode childNode = curNode.child.get(key);
					
					if(childNode == null ) continue;
					
					if(curNode == this) { // level 1 
						childNode.fail = this;
					}else {
						TrieNode failNode = curNode.fail; // 부모의 실패노드 
						
						// 부모 실패노드의 자식노드가 key가 아닌 경우 실패노드 거슬러 탐색하기
						while(failNode != this && failNode.child.get(key) == null) {
							failNode = failNode.fail;
						}
						
						// 부모 실패노드의 자식노드가 key인 경우 실패링크 연결 
						if(failNode.child.get(key) != null) {
							failNode = failNode.child.get(key);
						}
					
						childNode.fail = failNode;
					}
					
					// 실패링크 엔드노드가 output == true 이면, 해당 노드도 output
					if(childNode.fail.output) {
						childNode.output= true;
					}
					q.add(childNode);
				}
			}
		}
		
		public int ahoCorasick(String word) {
			TrieNode curNode = this;
			int cnt =0;
			for(int i=0; i<word.length(); i++) {
				int key = data.get(word.charAt(i));
				while(curNode != this && curNode.child.get(key) == null) {
					curNode = curNode.fail;
				}
				
				if(curNode.child.get(key) != null) {
					curNode = curNode.child.get(key);
				}
				
				if(curNode.output) {
					cnt++;
				}
			}
			return cnt;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		while(tc-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			String parent = br.readLine();
			String pattern = br.readLine();

			TrieNode trie = new TrieNode();
			trie.insert(pattern);
			for (int i = 0; i < m; i++) {
				for (int j = i + 1; j <m; j++) {
					trie.insert(reverseString(pattern,i,j+1));
				}
			}
			
			trie.computeFailFunc();
			sb.append(trie.ahoCorasick(parent)+"\n");
		}
		System.out.println(sb.toString());
	}
	
	public static String reverseString(String tmp, int s, int e) {
		StringBuilder sb = new StringBuilder();
		sb.append(tmp.substring(0, s));
		sb.append(new StringBuilder(tmp.substring(s, e)).reverse());
		sb.append(tmp.substring(e, tmp.length()));
		return sb.toString();
	  }
}