연습문제 > 숫자 변환하기

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

풀이 자체는 주석으로 모두 달아놨다.

지금까지 문제를 풀기 전에 알고리즘적 고민을 다양하게 해왔는데 코드를 작성하는 곳에 주석으로 달아놓는 것은 참조하기 쉽다는 편에서 좋은 것 같다.

#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
//BFS로 푸는 문제
//페어로 이루어진 큐 만들기 (숫자, 연산횟수)
//숫자에다가 가능한 연산해서 연산횟수 더하기 1 한 페어 만들기
//그 연산결과가 y보다 작고 중복이 아니라면 다시 큐에 넣기
//중복은 visited로 관리, 시간 복잡도만 고려하면 vector로도 가능할 듯 하지만 공간 복잡도 고려하여 unordered_set으로 관리
//중간에 y와 같은 연산결과 발견하면 연산횟수 반환
//큐가 모두 빌 때까지 반복, 그 때까지 답 안 나오면 -1 반환
int solution(int x, int y, int n) {
    if(x==y) return 0;
    int answer = 0;
    queue<pair<int, int>> que;
    unordered_set<int> visited;
    que.push({x,0});
    while(!que.empty()){
        int curr = que.front().first;
        answer = que.front().second;
        que.pop();
        if (visited.find(curr) != visited.end()) continue;
        else if(curr == y) return answer;
        else if(curr>y) continue;
        que.push({curr+n,answer+1});
        que.push({curr*2,answer+1});
        que.push({curr*3,answer+1});
        visited.insert(curr);
    }
    return -1;
}