[프로그래머스][JAVA] 숫자 변환하기

링크

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

프로그래머스

 

설명

BFS 나 DFS를 통해 backtracking 처럼 더해질 수 있는 경우의 수를 계산한다.

최대 숫자가 1,000,000 이기 때문에 그 이상은 체크하지 않는다.

 

각 BFS 단계마다 n만큼 더하거나, 2배를 곱해주거나, 3배를 곱해주면서

현재의 경우의 수가 y와 같아지는 지 찾는다.

찾았다면 현재 단계의 숫자를 반환한다.

 

풀이

import java.util.*;

class Solution {
    int answer = -1;
    
    public int solution(int x, int y, int n) {
        bfs(x, y, n);
        return answer;
    }
    
    private void bfs(int start, int goal, int add) {
        Set<Integer> calculateNumbers = new HashSet<>();
        calculateNumbers.add(start);
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start, 0});
        while(!q.isEmpty()) {
            int[] currentNumberInfo = q.poll();
            int current = currentNumberInfo[0];
            int calculateCount = currentNumberInfo[1];
            if (current == goal) {
                answer = calculateCount;
                break;
            }
        
            // 3가지 행동 시작
            // 더하기
            int addNum = current + add;
            // 2 곱하기
            int multi2Num = current * 2;
            // 3 곱하기
            int multi3Num = current * 3;
            if (current < goal || current < 1_000_000) {
                if (!calculateNumbers.contains(addNum)) {
                    q.add(new int[]{addNum, calculateCount + 1});
                    calculateNumbers.add(addNum);
                }
                
                if (!calculateNumbers.contains(multi2Num)) {
                    q.add(new int[]{multi2Num, calculateCount + 1});
                    calculateNumbers.add(multi2Num);
                }
                
                if (!calculateNumbers.contains(multi3Num)) {
                    q.add(new int[]{multi3Num, calculateCount + 1});
                    calculateNumbers.add(multi3Num);
                }
            }
        }
        
    }
}​