(2024-11-06) 2 문제 : 백준 - 14395 (4 연산)

 

간단한 BFS 문제이다. Queue를 통해 가능한 모든 경우를 탐색하면 된다.

 

주의해야 할 점은 세 가지 정도 있다.

1. long long 타입을 써야한다. (오버플로우 주의)

2. 방문체크해야됨 (중복을 방지하지 않으면 무한루프 발생. 본인은 unordered_set으로 방문체크 했다.)

3. 아스키 코드 순서에 맞게 Queue에 다음 원소를 삽입해야 함. ('*' -> '+' -> '-' -> '/' )

 

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int StartNumber = 0, TargetNumber = 0;
    std::cin >> StartNumber >> TargetNumber;

    std::queue<std::pair<long long, std::string>> Queue;
    Queue.push({ StartNumber, "" });

    std::unordered_set<long long> Check;

    while (Queue.size() > 0)
    {
        auto [CurNumber, CurSigns] = Queue.front();
        Queue.pop();

        if (CurNumber == TargetNumber)
        {
            if (CurSigns == "")
            {
                std::cout << 0;
                return 0;
            }

            std::cout << CurSigns;
            return 0;
        }

        long long MulValue = CurNumber * CurNumber;
        if (Check.find(MulValue) == Check.end())
        {
            Check.insert(MulValue);
            Queue.push({ MulValue, CurSigns + "*" });
        }

        long long AddValue = CurNumber + CurNumber;
        if (Check.find(AddValue) == Check.end())
        {
            Check.insert(AddValue);
            Queue.push({ AddValue, CurSigns + "+" });
        }

        long long SubValue = CurNumber - CurNumber;
        if (Check.find(SubValue) == Check.end())
        {
            Check.insert(SubValue);
            Queue.push({ SubValue, CurSigns + "-" });
        }
        
        if (CurNumber != 0)
        {
            long long DivValue = CurNumber / CurNumber;

            if (Check.find(DivValue) == Check.end())
            {
                Check.insert(DivValue);
                Queue.push({ DivValue, CurSigns + "/" });
            }
        }
    }

    std::cout << -1;

    return 0;
}