[백준 14395 C++][G5] 4연산

⭐️ 난이도

Gold 5

---

⭐️ 문제

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

14395번: 4연산

 

 

---

⭐️ Idea flow

 

이 문제의 내용을 정리해보자.

사칙연산만을 최소한으로 이용해서 s를 t로 바꾸려고 한다.
가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력하라. (사칙연산의 사전 순은 다음과 같다. * + - /)
s == t라면 0을, s를 t로 바꿀 수 없다면 -1을 출력하라.

 

연산할 수 있는 방법이 4가지로 정해져 있는데, 이를 최소한으로 사용해야 한다.

시작점과 끝점(목표)가 정해져 있고, 사용할 수 있는 방법이 정해져 있으므로, 최단 거리를 구하는 알고리즘 중 하나인

BFS 알고리즘을 사용하면 좋을 것 같다는 판단을 내렸다.

 

여기서 중요한 점은 "가능한 방법이 여러가지라면, 사전 순으로 앞서는 것을 출력하라"라는 부분이다.

여기서 두 가지 방법을 생각할 수 있는데,

1. 가능한 가짓수를 모두 저장하고 sort(정렬)해서 제일 앞의 것을 출력하는 것.

2. 애초부터 BFS할 때 연산의 순서를 사전 순으로 진행하는 것.

이다.

 

이 중에 우리가 사용할 방법은 2번이다.

메모리적인 면에서 봐도 1번은 모든 결과 값들을 저장해야 하고, 정렬을 위한 오버 로딩이 필요할 것이다.

하지만 2번을 사용하면 결과 값들을 저장하기 위한 별도의 메모리 공간이 필요 없고 또한 정렬을 위한 오버 로딩 또한 하지 않아도 된다.

 

BFS를 하면서 연산 순서를 * + - / 순으로 진행한다면 자동으로 사전순으로 방법을 찾게 될 것이다.

 

BFS를 사용하면 해당 수를 방문했는지의 여부인 isVisited 배열이 필요하다.

그런데 이 문제에서 값이 어디까지 올라갈지 알기 힘들기 때문에 unordered_set을 통해서 방문 여부를 확인할 것이다.

set처럼 하나의 원소만을 저장하는 것은 같지만, unordered_set은 hashmap방식으로 구현되어 있다는 차이점이 있다.

 

사칙 연산 값을 구하고, 만일 unordered_set에 값이 없다면 아직 방문을 안했다는 뜻이므로 q에 값을 push 한다.

만일 값이 unordered_set에 있다면 방문을 했다는 뜻이므로 행동을 하지 않고 넘어간다.

 

queue에 현재 정수 값뿐만 아니라, 출력 결과 값인 string도 같이 넣음으로써 현재 값이 원하는 값과 같다면 바로 출력할 수 있게 한다.

 

 

[전체적인 알고리즘]

1. 시작하는 값 s와 목표하는 값 t를 입력받는다.
   이 때, s와 t가 같다면 0을 출력하고 종료한다.
2. BFS를 진행할 queue와 방문 여부를 저장할 unordered_set 객체를 만든다.
    처음 시작은 s이므로, queue에 s와 ""를 push한다.
3. 이후 * + - / 연산을 차례대로 실행한다.
   만일 연산 결과 값이 unordered_set에 없다면 아직 방문하지 않았다는 뜻이다.
   따라서 현재 정수 값 cur과 결과 값을 담는 str에 현재 사용한 사칙연산을 추가해서 queue에 담는다.
   또한 cur에 이번에 방문했으므로 unordered_set에 cur값을 insert한다.
4. 위의 과정을 진행하다가 현재 값이 t가 된다면, str를 결과 값에 저장한다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <unordered_set>

#define INF 10000000000000
using namespace std;

// 14395 - 4연산
int s, t;
string result;
bool flag = false;

void input(){
    cin >> s >> t;
}

void solve(){
    unordered_set<long long> hashmap;
    queue<pair<long long, string>> q;
    q.push({s, ""});

    while(!q.empty()){
        long long cur = q.front().first;
        string str = q.front().second;
        q.pop();

        if(cur == t){
            flag = true;
            result = str;
            return;
        }
        long long next = cur * cur;
        if(hashmap.find(next) == hashmap.end()){
            hashmap.insert(next);
            q.push({cur * cur, str + "*"});
        }
        next = cur + cur;
        if(hashmap.find(next) == hashmap.end()){
            hashmap.insert(next);
            q.push({cur + cur, str + "+"});
        }
        next = cur - cur;
        if(hashmap.find(next) == hashmap.end()){
            hashmap.insert(next);
            q.push({cur - cur, str + "-"});
        }

        if(cur != 0){
            next = cur / cur;
            if(hashmap.find(next) == hashmap.end()){
                hashmap.insert(next);
                q.push({cur / cur, str + "/"});
            }
        }

    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    if(s == t){
        cout << "0";
    }
    else{
        solve();
        if(flag){
            cout << result;
        }
        else{
            cout << "-1";
        }
    }


    return 0;
}