[BOJ, C++]#14426_접두사 찾기, 검색 트리, Trie 자료 구조, Trie 검색 트리, 트리

#1. 문제

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

 

---

 

#2. 풀이

 

1. Trie 검색 트리

[자료구조]#8_Trie 검색 트리

#include <iostream>
#include <unordered_map>
using namespace std;

// 트라이 노드 정의
struct TrieNode {
    unordered_map<char, TrieNode*> children; // 자식 노드를 저장하기 위한 맵
    bool isEnd; // 단어의 끝을 표시하는 플래그
    TrieNode() : isEnd(false) {} // 생성자
};

// 트라이 클래스 정의
class Trie {
private:
    TrieNode* root; // 루트 노드

public:
    Trie() {
        root = new TrieNode(); // 루트 노드 생성
    }

    // 단어 삽입 메서드
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode(); // 새로운 자식 노드 생성
            }
            node = node->children[ch]; // 다음 노드로 이동
        }
        node->isEnd = true; // 단어의 끝임을 표시
    }

    // 단어 검색 메서드
    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                return false; // 해당 문자를 나타내는 자식 노드가 없으면 단어가 없음
            }
            node = node->children[ch]; // 다음 노드로 이동
        }
        return node->isEnd; // 단어의 끝인지 확인하여 반환
    }
};

Trie 검색 트리 자료구조는 문자열 탐색 작업에 특화된 트리 중 하나로, 트라이 검색 트리의 각 노드는 문자열의 특정 문자를 나타내며, 뒤에 오는 문자들을 자식 노드로 가지고 있는 트리 자료구조입니다.

 

2. Trie 검색 트리에서 탐색 작업

1. 집합 S를 트라이 자료구조로 구성합니다.
2. M개의 문자열들을 입력받습니다. 그리고, 트라이 자료구조에 대하여 입력받은 문자열을 검색합니다. 이때, 찾고자 하는 접두사가 트라이 자료구조의 루트 노드부터 차례대로 탐색을 진행하여 모두 존재할 때만 접두사로 인정해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/14426
*   @문제: 점두사 찾기
*   @설명
        1. Trie 검색 트리
        2. Trie Node 구조체, Trie 검색 트리 구조체, Trie 검색 트리의 삽입, 검색 함수 외우기
*/


#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int N, M;
int ans;

//@트리 노드
struct TrieNode
{
    unordered_map<char, TrieNode*> children;
    bool IsTerminal;
    TrieNode()
    : IsTerminal(false) {}
};

class Trie
{
private:
    TrieNode* root;

public:
    //@생성자
    Trie()
    {
        root = new TrieNode();
    }

    //@삽입
    void Insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch]; 
        }
        node->IsTerminal = true;
    }

    //@검색
    bool Search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                return false; 
            }
            node = node->children[ch]; 
        }
        return true;
    }
};


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    //@트라이 객체
    Trie* S = new Trie();

    //@트라이 검색 트리 구성
    for(int i=0; i<N; ++i)
    {
        string str;
        cin >> str;

        //@집합 S 구성
        S->Insert(str);
    }

    while(M--)
    {
        string str;
        cin>> str;

        if(S->Search(str))
        {
            ans++;
        }
    }    

    cout << ans;

    return 0;
}

 

---