[ 백준 3407 ] 맹세 (C++)

백준의 맹세(3407) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는, 원소 주기율표에 있는 원소들로만 해당 단어를 읽을 수 있는지 판단하는 문제이다... 하...

   일단 이 문제를 풀기전에, 저 원소들을 다 적어서 어딘가에 저장을 해줘야 한다. 비교를 해줘야 하기 때문이다.

   혹시나, 아직 코드에 이 표를 적지 않으신분들을 위해서 올려두겠다 !

string List[] = { "h", "li", "na", "k", "rb", "cs", "fr", "be", "mg", "ca", "sr", "ba", "ra", "sc", "y", "ti", "zr", "hf", "rf", "la", "ac",
                  "v", "nb", "ta", "db", "ce", "th", "cr", "mo", "w", "sg", "pr", "pa", "mn", "tc", "re", "bh", "nd", "u", "fe", "ru", "os",
                  "hs", "pm", "np", "co", "rh", "ir", "mt", "sm", "pu", "ni", "pd", "pt", "ds", "eu", "am", "cu", "ag" ,"au", "rg", "gd", "cm",
                  "zn", "cd", "hg", "cn", "tb", "bk", "b", "al", "ga", "in", "tl", "dy", "cf", "c", "si", "ge", "sn", "pb", "fl", "ho", "es",
                  "n", "p", "as", "sb", "bi", "er", "fm", "o", "s", "se", "te", "po", "lv", "tm", "md", "f", "cl", "br", "i", "at", "yb", "no",
                  "he", "ne", "ar", "kr", "xe", "rn","lu", "lr" };

    위의 표 복사해서 사용하시면 됩니다 !  ( 참고로 위의 원소들의 갯수는 총 114개 )

    문제 풀이 과정은 생각보다 어렵지 않다. 본인은, 문자열의 Index번호를 이용해서 접근해주었다.

    탐색은 BFS를 이용해서 탐색해주었는데, 주어진 입력 문자열의 0번 Index부터 쭉 진행해 나가면서, 위의 List와 문자를 비교해서

    같은 문자가 있다면 Queue에 넣어주면서 반복해주었다.

    탐색 과정은 딱히 어려운 내용이 없으므로 소스코드만 참고하더라도 쉽게 이해할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<string>
#include<cstring>
 
#define endl "\n"
#define Range 114
using namespace std;
 
string List[] = { "h", "li", "na", "k", "rb", "cs", "fr", "be", "mg", "ca", "sr", "ba", "ra", "sc", "y", "ti", "zr", "hf", "rf", "la", "ac",
                  "v", "nb", "ta", "db", "ce", "th", "cr", "mo", "w", "sg", "pr", "pa", "mn", "tc", "re", "bh", "nd", "u", "fe", "ru", "os",
                  "hs", "pm", "np", "co", "rh", "ir", "mt", "sm", "pu", "ni", "pd", "pt", "ds", "eu", "am", "cu", "ag" ,"au", "rg", "gd", "cm",
                  "zn", "cd", "hg", "cn", "tb", "bk", "b", "al", "ga", "in", "tl", "dy", "cf", "c", "si", "ge", "sn", "pb", "fl", "ho", "es",
                  "n", "p", "as", "sb", "bi", "er", "fm", "o", "s", "se", "te", "po", "lv", "tm", "md", "f", "cl", "br", "i", "at", "yb", "no",
                  "he", "ne", "ar", "kr", "xe", "rn","lu", "lr" };
 
string Inp;
int Len;
bool Visit[50000];
 
void Initialize()
{
    Inp.clear();
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> Inp;
    Len = Inp.length();
}
 
void BFS(int a)
{
    bool Flag = false;
    queue<int> Q;
    Q.push(a);
    Visit[a] = true;
 
    while (Q.empty() == 0)
    {
        int Idx = Q.front();
        Q.pop();
 
        if (Idx == Len)
        {
            Flag = true;
            break;
        }
 
        string Temp, Temp2;
        Temp = Temp2 = "";
        Temp = Temp + Inp[Idx];
        Temp2 = Temp2 + Inp[Idx] + Inp[Idx + 1];
 
        for (int i = 0; i < Range; i++)
        {
            if (Temp == List[i] && Visit[Idx + 1] == false)
            {
                Visit[Idx + 1] = true;
                Q.push(Idx + 1);
            }
            if (Temp2 == List[i] && Visit[Idx + 2] == false)
            {
                Visit[Idx + 2] = true;
                Q.push(Idx + 2);
            }
        }
    }
 
    if (Flag == true) cout << "YES" << endl;
    else cout << "NO" << endl;
}
 
void Solution()
{
    BFS(0);
 
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for(int T =1 ; T<=Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}