14395번 4연산

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

일반적인 BFS 문제이다.

복습하고, 다시 풀어볼 문제이긴 하다.

한 번에 맞을 줄은 몰랐다.

#include <bits/stdc++.h>
 
using namespace std;
 
long long s, t;
 
queue<pair<long long, string> > q;
 
map<long long, int> m;
 
vector<char> v = { '*', '+', '-', '/' };
 
int main(void)
{
    scanf("%lld %lld", &s, &t);
 
    if (s == t)
    {
        printf("0\n");
        return 0;
    }
 
    q.push({ s, "" });
 
    m[s] = 1;
 
    while (!q.empty())
    {
        long long now = q.front().first;
        string s = q.front().second;
 
        q.pop();
 
        if (now == t)
        {
            cout << s << '\n';
            return 0;
        }
 
        for (int i = 0; i < 4; i++)
        {
            if (i == 0)
            {
                if (!m.count(now * now))
                {
                    q.push({ now * now, s + v.at(i) });
                    m[now * now] = 1;
                }
            }
            else if (i == 1)
            {
                if (!m.count(now + now))
                {
                    q.push({ now + now, s + v.at(i) });
                    m[now + now] = 1;
                }
            }
            else if (i == 2)
            {
                if (!m.count(now - now))
                {
                    q.push({ now - now, s + v.at(i) });
                    m[now - now] = 1;
                }
            }
            else if (i == 3)
            {
                if (now != 0 && !m.count(now / now))
                {
                    q.push({ now / now, s + v.at(i) });
                    m[now / now] = 1;
                }
            }
        }
    }
 
    printf("-1\n");
 
    return 0;
}