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

처음엔 DFS로 완전탐색 방식으로 구현해봤는데, 테스트케이스 절반에서 시간초과가 나서 BFS로 바꾸었더니

시간초과 없이 전부 맞출 수 있었습니다. 문제를 풀 때,  BFS를 사용할 수 있으면 BFS가 높은 점수를 받기에는

더 좋은 것 같습니다. 

 

 

#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
 
using namespace std;
 
// DFS로 완전탐색때는 시간초과 났었기때문에 BFS로 다시 품
 
bool flag = false;
int total = INT_MAX;
int visited[1000001];
 
void BFS(int a, int b, int n)
{
    int dx[3] = {2,3,n};
    int start = a;
    queue<pair<int,int>> Q;
    Q.push({start,0});
    visited[start] = 1;
    
    while(!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();
        
        if (cur.first == b)
        {
            flag = true;
            if (cur.second < total)
                total = cur.second;
        }
        
        for (int i=0;i<3;i++)
        {
            int next;
            if (i==2)
                next = cur.first + dx[i];
            else
                next = cur.first * dx[i];
            
            if (next > b || visited[next] == 1)
                continue;
            
            visited[next] = 1;
            Q.push({next,cur.second+1});
        }
    }
    
}
 
int solution(int x, int y, int n) {
    BFS(x,y,n);
    if (flag == false)
        return -1;
    
    return total;
}