[Programmers] 숫자 변환하기(LV.2)

풀이 소요시간 : 15분

BFS 로 최단 시간을 구하는 방식을 사용했다. 빠르게 풀 수 있었지만 DP 방식으로 푼 사람의 수도 많아보인다. 이번에는 unordered_map 을 사용하여 방문체크를 하는 방식으로 리팩토링을 해보았다. 이차원 배열 방문체크는 해보지 않았지만, 우선 1차원 배열에서는 뛰어난 성능을 보이고 코드 또한 단순화되는 것 같다.

전체 코드(unordered_map 사용)

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

unordered_map<int, int> Map;

int Y;
int X;

int Bfs(int x, int n) {
    
    queue<pair<int, int>> Q;
    Q.push({x, 0});
    
    while(!Q.empty()) {
        
        int px = Q.front().first;
        int time = Q.front().second;
        Q.pop();
        
        if(px == Y) return time;
        
        // 범위 초과 & 방문 가능 고려
        
        if(px + n <= Y && Map[px + n] == 0) {
            Map[px + n]++;
            Q.push({px + n, time + 1});
        }
    
        
        if(px * 2 <= Y && Map[px * 2] == 0) {
            Map[px * 2]++;
            Q.push({px * 2, time + 1});
        }
        
        
        if(px * 3 <= Y && Map[px * 3] == 0) {
            Map[px * 3]++;
            Q.push({px * 3, time + 1});
        }
        
        
    }
    
    return -1;
}


int solution(int x, int y, int n) {
    
    X = x;
    Y = y;
    Map[x]++;
    return Bfs(x, n);
    
}