프로그래머스 154538 - 숫자 변환하기 (Lv.5)

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

// 프로그래머스 154538 - 숫자 변환하기 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/154538

// 문제 설명
// 자연수 x를 y로 변환하려 한다. 사용할 수 있는 연산은 세 가지로, 현재 값 n_cur에 대해
//   n_cur + n,  n_cur * 2,  n_cur * 3
// 중 하나를 골라 바꿀 수 있다. x를 y로 만드는 데 필요한 최소 연산 횟수를 반환하고,
// 만들 수 없으면 -1을 반환하라.

// 제약 조건
// 1 <= x <= y <= 1,000,000
// 1 <= n < y

// Example
// Input : x = 10, y = 40, n = 5    Output: 2   (10 -> 20 -> 40, x2 두 번)
// Input : x = 10, y = 40, n = 30   Output: 1   (10 -> 40, +30 한 번)
// Input : x = 2,  y = 5,  n = 4    Output: -1  (2 -> 4/6/6, 5에 닿을 수 없다)

// 접근 — 상태 그래프 위의 BFS
// 세 연산 모두 값을 "키우기만" 한다(n >= 1, 배수 >= 2). 그래서 한 번 y를 넘어간 값은
// 절대 y로 돌아올 수 없고, 탐색 범위를 [x, y]로 가둘 수 있다 — 상태 수가 최대 10^6으로 유한.
// 정점 = 현재 수, 간선 = 세 연산, 간선 비용은 전부 1.
// 비용이 균일하므로 BFS로 처음 도달한 순간이 곧 최단 = 최소 연산 횟수 (다익스트라 불필요).
// dist는 방문 표시와 거리 저장을 겸하되 +1 인코딩(도달 = 1부터)을 써서
// "미방문 0"과 "0회 만에 도달"이 충돌하지 않게 한다.
// 큐가 비도록 y에 닿지 못하면 도달 불가이므로 -1.
// 시간 O(y), 공간 O(y)

#include <queue>
#include <cstring>

using namespace std;

int dist[1000001];          // 0 = 미방문, 그 외 = 연산 횟수 + 1

int solution(int x, int y, int n) {
    memset(dist, 0, sizeof(dist));      // 여러 번 호출돼도 이전 상태가 남지 않게

    queue<int> q;
    q.push(x);
    dist[x] = 1;                        // +1 인코딩: 미방문 0과 "0회 도달"을 구분

    while (!q.empty()) {
        int here = q.front(); q.pop();
        if (here == y) return dist[here] - 1;

        for (int next : { here + n, here * 2, here * 3 })
            if (next <= y && !dist[next]) {
                dist[next] = dist[here] + 1;
                q.push(next);
            }
    }
    return -1;
}

정리

• 이 문제가 BFS로 풀리는 근거는 연산의 단조성이다. +n·×2·×3이 전부 값을 키우기만 하므로 y를 넘어선 값은 두 번 다시 y로 내려올 수 없고, 그래서 next <= y 가지치기가 정답을 깎지 않는다. 상태 공간이 [x, y] ⊆ [1, 10⁶]로 닫히는 순간 “무한 그래프”가 정점 100만 개짜리 유한 그래프가 된다 — 가지치기의 정당성을 먼저 증명하고 나서 BFS를 얹는 순서가 중요하다.
• 간선 비용이 전부 1이라 BFS 최초 도달 = 최단이다. 비용이 제각각이었다면 다익스트라가 필요하고, 0과 1 두 종류였다면 덱을 쓰는 0-1 BFS였을 것이다. “최소 횟수”라는 표현을 보면 먼저 간선 가중치가 균일한지부터 확인한다.
• visited와 dist를 하나로 합치기 위해 +1 인코딩을 썼다. 도달을 1부터 세고 마지막에 - 1을 빼면 미방문 0과 “0회 만에 도달(x == y)”이 구분된다. 별도의 visited 배열을 두는 것보다 배열 하나가 줄고, x == y인 입력에서 0을 정확히 돌려준다.
• 전역 배열을 쓸 때의 함정: 채점기가 같은 프로세스에서 solution을 여러 번 부르면 이전 호출의 방문 흔적이 남아 두 번째부터 오답이 난다. 그래서 진입부에서 memset으로 리셋한다. 로컬에서 같은 입력을 두 번 호출해 결과가 유지되는지 확인하는 게 이 부류의 최소 회귀 테스트다.
• 정방향 BFS 대신 역방향(y → x) 탐색도 성립한다. y에서 /2·/3(나눠떨어질 때만)·-n으로 내려가면 도달 가능한 상태가 훨씬 적어 빠르지만, “나눠떨어지는가” 분기가 붙는다. 정방향은 조건 없이 세 갈래를 그대로 밀 수 있어 코드가 짧고, 상한 O(y)로도 충분히 여유가 있어 정방향을 택했다. 커리큘럼 100번.
• 검증: 예제 3개(2, 1, -1) 통과, x == y인 (7, 7, 3) → 0, 같은 입력 재호출 시 동일 결과(전역 배열 리셋 확인), 최대 규모 (1, 1000000, 1) → 19가 0.011초 (MSVC /O2 /std:c++17).

핵심 요약 — 세 연산이 값을 키우기만 한다는 단조성 덕에 상태 공간이 [x, y]로 닫히고, 간선 비용이 모두 1이라 BFS 최초 도달이 그대로 최소 연산 횟수가 된다. dist 하나로 방문과 거리를 겸하되 +1 인코딩을 써야 “미방문 0”과 “0회 도달”이 섞이지 않는다.