프로그래머스 연습문제 숫자 변환하기 [JAVA] - 23년 3월 29일

이 문제와 비슷한게 백준의 물통 문제가 있다.
좋은 문제이므로 같이 풀어보면 좋을 듯 하다. 이 문제를 풀었던 경험 때문에 해당 문제도 보자마자 BFS로 풀 수 있었다.

(※나는 물통 문제 덕분에 코테에 대해서 무언가 조금의 깨달음이 있었다.)

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int start, int target, int plus) {
        //bfs 풀이
        Deque<int[]> deque = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();

        deque.add(new int[]{start, 0}); // 시작값, count

        while (!deque.isEmpty()) {
            int[] curValArr = deque.pollFirst();
            int curVal = curValArr[0];
            int curCount = curValArr[1];
            if (curVal == target) {
                return curCount;
            }

            //curVal에 n 더하기
            validateNextValue(target, deque, visited, curCount, curVal + plus);

            //curval에 2 곱하기
            validateNextValue(target, deque, visited, curCount, curVal * 2);

            //curval에 3 곱하기
            validateNextValue(target, deque, visited, curCount, curVal * 3);
        }

        return -1;
    }

    private void validateNextValue(int target, Deque<int[]> deque, Set<Integer> visited, int curCount, int nextValue) {
        if (!visited.contains(nextValue) && nextValue <= target) {
            deque.add(new int[]{nextValue, curCount + 1});
            visited.add(nextValue);
        }
    }
}