숫자 변환하기

문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같이 3가지입니다.

1. x에 n을 더합니다.
2. x에 2를 곱합니다.
3. x에 3을 곱합니다.

자연수 x, y, n이 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 구하는 프로그램을 작성하는 문제입니다. 만약 x를 y로 만들 수 없다면 -1을 반환해야 합니다.

• 입력: 시작 숫자 x, 목표 숫자 y (1 ≤ x ≤ y ≤ 1,000,000), 더할 숫자 n (1 ≤ n < y)
• 출력: 변환에 필요한 최소 연산 횟수 (변환 불가 시 -1)

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

풀이: 방문 배열과 BFS를 활용한 최단 거리 탐색

주어진 연산을 간선으로 생각하고, 시작 숫자 x에서 목표 숫자 y로 가는 **최단 경로(최소 연산 횟수)**를 찾는 전형적인 BFS(너비 우선 탐색) 풀이입니다.

• 방문 배열(visited) 설정: 숫자 범위의 최댓값인 1,000,000까지 수용할 수 있는 배열을 생성합니다. 이 배열은 방문 여부와 함께 연산 횟수를 저장하는 역할을 합니다.
• 초기화 및 방문 처리 팁: 시작점 x를 큐에 넣고 visited[x] = 1로 초기화합니다. 연산 횟수가 0회인 상태를 1로 시작하는 이유는, 배열의 기본 초기값인 0(미방문)과 구분하기 위해서입니다.
• BFS 탐색: 큐에서 현재 숫자(cur)를 꺼내어 목표 숫자 y인지 확인합니다. 도달했다면 즉시 탐색을 종료(break)합니다. 도달하지 못했다면 가능한 3가지 다음 상태(cur + n, cur * 2, cur * 3)를 확인합니다. 계산된 다음 숫자가 1,000,000을 넘지 않고, 아직 방문하지 않은 숫자(visited[nx] == 0)라면 큐에 넣고 이전 연산 횟수에 1을 더해 기록합니다(visited[cur] + 1).
• 결과 반환의 깔끔한 처리: 반복문이 끝난 후 visited[y] - 1을 반환합니다. 만약 y에 도달했다면 초기값 1을 상쇄하여 올바른 최소 횟수가 반환됩니다. 만약 y에 도달할 수 없었다면 visited[y]는 기본값인 0으로 남아있게 되며, 여기서 1을 빼면 문제에서 요구하는 실패 조건인 -1이 자연스럽게 도출됩니다.

코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        Queue<Integer> q = new LinkedList<>();
        int[] visited = new int[1000001];
        
        q.add(x);
        visited[x] = 1; // 미방문 상태(0)와 구분하기 위해 1부터 시작
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            
            // 목표 숫자에 도달하면 탐색 종료
            if (cur == y) {
                break;
            }
            
            // 3가지 연산에 대해 다음 상태 탐색
            for (int nx : new int[] {cur + n, 2 * cur, 3 * cur}) {
                // 범위 초과 또는 이미 방문한 숫자인 경우 패스
                if (nx > 1000000 || visited[nx] != 0) continue;
                
                q.add(nx);
                visited[nx] = visited[cur] + 1;
            }
        }
        
        // 도달 성공 시: (기록된 값 - 1)이 실제 횟수
        // 도달 실패 시: 0(초기값) - 1 = -1 반환
        return visited[y] - 1;
    }
}

알고리즘 분류

그래프 탐색 (Graph Traversal), 너비 우선 탐색 (BFS, Breadth-First Search)