[C++] 프로그래머스 숫자 변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

풀이

최단 거리 문제이기 때문에 BFS를 사용해서 문제를 해결한다.

이때, x를 시작점으로 잡아서 증가하는 방식으로 y와 같아지는 경우를 찾는 경우, *2, *3 연산이 모두 큐에 들어갈 수 있어 시간 초과가 난다.

따라서, y를 시작점으로 해서 2, 3으로 나누어 떨어지는 경우에만 큐에 넣어줘야 효율적인 코드가 된다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(int x, int y, int n) {
    int answer = 0;
    if (x==y) return 0;
    queue<pair<int, int>> q;
    q.push({y, 0});
    
    while (!q.empty()){
        pair<int, int> v=q.front();
        q.pop();
        
        if (v.first-n >= x) {
            if (v.first-n==x){
                answer=v.second+1;
                break;
            }
            q.push({v.first-n, v.second+1});
        }
        if (v.first%2==0 && v.first/2 >= x) {
            if (v.first/2==x){
                answer=v.second+1;
                break;
            }
            q.push({v.first/2, v.second+1});
        }
        if (v.first%3==0 && v.first/3 >= x) {
            if (v.first/3==x){
                answer=v.second+1;
                break;
            }
            q.push({v.first/3, v.second+1});
        }
    }
    if (answer==0) answer= -1;
    return answer;
}