[Programmers] 숫자 변환하기

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

프로그래머스

문제 설명

x가 y가 되도록 하는 최소 연산 횟수를 구하는 문제이다. 가장 바로 떠오른 방법은 DFS였고 이를 활용했으나 시간 초과가 발생하여 Set을 활용한 BFS 방식으로 바꾸어 해결하였다. 임시 Set을 두었는데 이유는 연산 횟수를 정확히 세기 위함이다.

BFS

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = convertBFS(x, y, n);
        
        return answer;
    }
    
    private int convertBFS(int x, int y, int n) {
        int depth = 0;
        Set<Integer> set = new HashSet<>();
        Set<Integer> tmp = new HashSet<>();
        set.add(x);
        
        while(!set.isEmpty()) {
            if (set.contains(y)) {
                return depth;
            }
            
            tmp = new HashSet<>();
            for (int elem : set) {
                int a = elem + n;
                int b = elem * 2;
                int c = elem * 3;
                
                if (a <= y) tmp.add(a);
                if (b <= y) tmp.add(b);
                if (c <= y) tmp.add(c);
            }

            set = tmp;
            depth += 1;
        }
        
        return -1;
    }
}

DFS - 시간 초과, 스택 오버플로우 오류

class Solution {
    private int answer = Integer.MAX_VALUE;
    
    public int solution(int x, int y, int n) {
        convert(x, y, n, 0);
        
        return answer;
    }
    
    private void convert(int x, int y, int n, int depth) {
        if (x > y) {
            return;
        } else if (x == y) {
            answer = Math.min(answer, depth);
            return;
        } else {
            convert(x + n, y, n, depth + 1);
            convert(x * 2, y, n, depth + 1);
            convert(x * 3, y, n, depth + 1);
        }
    }
}