숫자 변환(BFS)

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

처음에 문제를 읽고 브루트포스로 각 x마다 3가지 경우를 다 해봐야되나 생각했지만, x와 y의 최대 값이 백만으로 크기 때문에 비효율적이고 시간 초과가 발생할 것이라고 생각했다.

최소 연산 횟수를 구하는 문제이고 이것은 최단거리 문제와 유사해보였다.
각 수를 정점으로 보고, 연산을 간선으로 보며 너비 우선 탐색인 BFS로 문제를 해결하는 것이 가장 적합해보였다.

✅ 구현 코드

#include <vector>
#include <queue>

using namespace std;

int solution(int x, int y, int n)
{
    queue<pair<int, int>> q;
    vector<bool> visited(y + 1, false);

    q.push({ x, 0 });
    visited[x] = true;

    while (!q.empty())
    {
        auto [cur, cnt] = q.front(); q.pop();

        if (cur == y) return cnt;

        vector<int> nexts = { cur + n, cur * 2, cur * 3 };

        for (int next : nexts)
        {
            if (next <= y && !visited[next])
            {
                visited[next] = true;
                q.push({ next, cnt + 1 });
            }

        }
    }

    return -1;
}

queue를 사용해 (현재 x값, 연산 횟수)를 pair로 저장하도록 했다.
그리고  visited 배열을 추가해 이미 방문한 숫자 x를 기록해 중복 연산을 방지하였다.

루프를 돌며 3가지 연산 결과를 nexts 배열에 저장한 뒤, 방문한 숫자가 아니면 queue에 등록하여 y값을 찾는 방식으로 간단하게 해결되었다.