[알고리즘] 코테 유형 분석 22. 트라이

안녕하세요 이번 시간에는 트라이(trie)에 대해 알아보는 시간을 갖도록 하겠습니다.

트라이란 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료 구조입니다. 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용하여 검색을 수행합니다.

트라이를 생성하는 방식은 다음과 같습니다.

1. Node 클래스 생성 : 각 노드 아래에 존재 가능한 노드 종류의 집합과 리프 노드 여부를 확인할 수 있는 클래스를 생성합니다.
   --> 이 때 노드 종류의 개수가 N일 경우 트라이는 N진 트리 형태로 나타납니다.
2. 단어를 한 글자씩 차레로 읽으면서 각 단어의 인덱스를 구합니다.
3. 현재 노드 아래의 노드 리스트에 해당 단어 인덱스의 값이 존재하지 않는다면(null) 새로운 노드를 생성합니다.
   (if(curr.next[idx] == null) curr.next[idx] = new Node();)
   --> 이 때 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태(null)이 됩니다.
4. 다음 노드로 현재 노드를 이동시킵니다.
5. 마지막 탐색 시 리프 노드를 체크합니다.

트라이에서 단어를 읽는 방식은 다음과 같습니다.

1. 단어를 한 글자씩 차례로 읽으면서 각 단어의 인덱스를 구합니다.
2. 현재 단어의 인덱스가 현재 노드 아래에 존재하지 않는다면(null) 다른 단어이므로 break 합니다.
3. 다음 노드로 현재 노드를 이동시킵니다.
4. 마지막까지 도착하고 리프 노드까지 맞을 경우 존재하는 단어입니다.

백준 14425(문자열 집합) 문제를 통해 트라이를 구현해보겠습니다. N개의 문자열 집합 S에 입력으로 주어지는 M개의 문자열 중 포함되어 있는 것이 몇 개인지를 구하는 문제입니다. 각 단어가 영어로 주어져있기 때문에 알파벳 개수인 26진 트리의 트라이를 구현합니다.

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

class Main{
    static int N,M;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Node root = new Node();

        while(N-- >0){
            String word = br.readLine();
            Node curr = root;
            for(int i=0;i<word.length();i++){
                int idx = word.charAt(i) - 'a';
                if(curr.next[idx] == null) curr.next[idx] = new Node();
                curr = curr.next[idx];
                if(i == word.length()-1) curr.isEnd = true;
            }
        }

        int cnt = 0;
        while(M-- >0){
            String word = br.readLine();
            Node curr = root;
            for(int i=0;i<word.length();i++){
                int idx = word.charAt(i) - 'a';
                if(curr.next[idx] == null) break;
                curr = curr.next[idx];
                if(i == word.length()-1 && curr.isEnd) cnt++;
            }
        }
        System.out.println(cnt);
    }

    static class Node{
        Node[] next = new Node[26];
        boolean isEnd;
    }
}