[BOJ/Platinum 3] 백준 19585 전설(C++)

문제 링크

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

19585번: 전설

 

문제

Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수상할 수 있을지 전설에 기반해 알려주는 프로그램을 작성하자.

입력

첫째 줄에는 색상의 종류 C와 닉네임의 개수 N이 주어진다. (1 ≤ C, N ≤ 4,000)

다음 C개의 줄에는 색상 이름 C개가 한 줄에 하나씩 주어진다. 색상 이름은 중복되지 않는다.

다음 N개의 줄에는 Sogang ICPC Team 구성원들의 닉네임 N개가 한 줄에 하나씩 주어진다. 닉네임도 중복되지 않는다.

다음 줄에는 팀의 개수 Q가 주어진다. (1 ≤ Q ≤ 20,000)

다음 Q개의 줄에는 팀명 Q개가 한 줄에 하나씩 주어진다. 팀명은 중복되지 않는다.

모든 색상 이름의 길이와 닉네임의 길이는 1,000글자를 넘지 않는다. 모든 팀명은 2,000글자를 넘지 않는다. 모든 문자열은 알파벳 소문자로만 이루어져 있다.

출력

팀명이 입력된 순서대로, 전설에 따라 해당 팀이 다음 리저널에서 수상할 수 있다면 Yes, 아니라면 No를 출력한다.

예제 입력 1

4 3
red
blue
purple
orange
shift
joker
noon
5
redshift
bluejoker
purplenoon
orangeshift
whiteblue

예제 출력 1

Yes
Yes
Yes
Yes
No

알고리즘 분류

• 트라이

풀이

트라이를 2개를 선언하고 색상 이름과 닉네임을 각각 insert한다. 여기서 닉네임은 역순으로 insert를 함으로써 팀명이 존재하는지를 탐색할 때 색상 이름과 닉네임의 경계가 맞닿으면 다음 리저널에서 수상할 수 있는 팀명이라고 판단한다.

Q개의 팀명을 입력받고 한 번은 첫 번째 문자부터 색상 트라이를 탐색하여 현재 문자까지 탐색했을 때 색상이 존재한다면, 즉 isEnd가 true라면 현재 Index까지 왔을 때 색상이 존재한다고 기록한다. 다음은 역순으로 닉네임 트라이를 탐색하여 마찬가지로 존재하는 닉네임이 있는지를 기록한다.

마지막으로 팀명에 존재하는 색상 이름과 닉네임의 경계가 맞닿는 경우가 존재하는지 파악한다. 0번째 Index부터, 현재 Index까지 탐색했을 때 색상이 존재하는지와 바로 다음 Index까지 탐색했을 때 닉네임이 존재하는지를 파악하고 둘 다 존재하는 경우가 있다면 해당 팀명은 다음 리저널에서 수상할 수 있는 팀명이므로 Yes를 출력한다.

그런 경우가 없다면 No를 출력한다.

코드

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

using namespace std;
struct TRIE {
    bool isEnd;
    vector<pair<char, TRIE*> > Child;

    TRIE() {
        isEnd = false;
        Child.clear();
    }

    void insert_Pattern(string Pattern) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Pattern.size(); i++) {
            char Now = Pattern[i];

            bool Flag = false;
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    Flag = true;
                    NowTrie = A.second;
                    break;
                }
            }
            if (!Flag) {
                NowTrie->Child.push_back(make_pair(Now, new TRIE));
                NowTrie = NowTrie->Child.back().second;
            }
        }

        NowTrie->isEnd = true;
    }
};

int C, N, Q;
string S;
bool Color[MAX], Nickname[MAX];

void init() {
    for (int i = 0; i < MAX; i++) {
        Color[i] = false;
        Nickname[i] = false;
    }
}

bool query(TRIE* Root1, TRIE* Root2) {
    TRIE* ColorTrie = Root1;
    TRIE* NicknameTrie = Root2;
    
    for (int i = 0; i < S.size(); i++) {
        char Now = S[i];
        bool Flag = false;
        for (auto A : ColorTrie->Child) {
            if (A.first == Now) {
                Flag = true;
                ColorTrie = A.second;
                break;
            }
        }
        if (!Flag) {
            break;
        }
        if (ColorTrie->isEnd) {
            Color[i] = true;
        }
    }
    
    for (int i = ((int)S.size() - 1); i >= 0; i--) {
        char Now = S[i];
        bool Flag = false;
        for (auto A : NicknameTrie->Child) {
            if (A.first == Now) {
                Flag = true;
                NicknameTrie = A.second;
                break;
            }
        }
        if (!Flag) {
            break;
        }
        if (NicknameTrie->isEnd) {
            Nickname[i] = true;
        }
    }
    
    for (int i = 0; i < ((int)S.size()); i++) {
        if (Color[i] && Nickname[i + 1]) {
            return true;
        }
    }
    return false;
}

void input() {
    TRIE* ColorTrie = new TRIE();
    TRIE* NicknameTrie = new TRIE();
    cin >> C >> N;
    for (int i = 0; i < C; i++) {
        cin >> S;
        ColorTrie->insert_Pattern(S);
    }
    for (int i = 0; i < N; i++) {
        cin >> S;
        reverse(S.begin(), S.end());
        NicknameTrie->insert_Pattern(S);
    }
    cin >> Q;
    while (Q--) {
        init();
        cin >> S;
        bool Answer = query(ColorTrie, NicknameTrie);
        if (Answer) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    };
    delete ColorTrie;
    delete NicknameTrie;
}

int main() {
    FASTIO
    input();

    return 0;
}