[BFS] 14395번 4연산

14395번 4연산

 

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

 

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s * s; (출력: *)
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

 

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 10⁹)

 

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

 

예제 입력

7 392

7 256

4 256

7 7

7 9

10 1

 

예제 출력

+*+

/+***

**

0

-1

/

 

해결방법

BFS 탐색을 통해 가능한 정답 중, 사전 순으로 맨 앞의 답을 출력하는 문제이다

 

먼저 문제에는 N ≤ 10⁹ 라는 조건이 있다

단순 BFS 탐색을 한다면 중복검사에 O(1,000,000,000) 이라는 시간복잡도로 시간초과가 발생할 것이다

따라서 set을 사용하여 log N 으로 시간복잡도를 줄여야한다

 

// 곱하기
if(num*num <= MAX){
    if(visited.find(to_string(num*num)) == visited.end()){
        q.push(Number(num*num,op+"*"));
        visited.insert(to_string(num*num));
    }
}

 

 

⭐️ 사전순 정렬 ⭐️

문제에서는 여러개의 답이 존재할 경우 사전 순으로 앞서는 것을 출력하라고 한다

굳이 사전순으로 정렬하지 않고 BFS 탐색에서 * + - / 순서로 탐색을 진행한다면??

알아서 * + - / 순서대로 탐색이 진행될것이다!!

 

⭐️ 정수형 범위 ⭐️

처음 코드를 실행하고 나서는 틀렸습니다 가 나왔다

이유를 모르겠어서 검색을 해보니 n의 값이 10억 까지 될 수 있는데 int 를 사용했기 때문이었다

자료형을 long long 으로 바꿔주니 문제가 간단히 해결됐다!!

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 1000000000
#define INF 987654321
using namespace std;

struct Number {
    long long num;
    string op;
    
    Number() {}
    Number(long long _num,string _op) : num(_num),op(_op) {}
};

long long s,t;
set<string> visited;

void bfs(){
    queue<Number> q;
    q.push(Number(s,""));
    visited.insert(to_string(s));
    
    while(!q.empty()){
        long long num = q.front().num;
        string op = q.front().op;
        q.pop();
        
        if(num == t){
            if(op!="")
                cout << op << "\n";
            else
                cout << 0 << "\n";
            return;
        }
        
        // 곱하기
        if(num*num <= MAX){
            if(visited.find(to_string(num*num)) == visited.end()){
                q.push(Number(num*num,op+"*"));
                visited.insert(to_string(num*num));
            }
        }
        
        // 더하기
        if(num+num <= MAX){
            if(visited.find(to_string(num+num)) == visited.end()){
                q.push(Number(num+num,op+"+"));
                visited.insert(to_string(num+num));
            }
        }
        
        // 빼기
        if(num-num > 0){
            if(visited.find(to_string(num-num)) == visited.end()){
                q.push(Number(num-num,op+"-"));
                visited.insert(to_string(num-num));
            }
        }
        
        // 나누기
        if(num != 0){
            if(visited.find(to_string(num/num)) == visited.end()){
                q.push(Number(num/num,op+"/"));
                visited.insert(to_string(num/num));
            }
        }
        
    }
    cout << -1 << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> s >> t;
    
    bfs();
    
    return 0;
}