(Java) 프로그래머스 - 숫자 변환하기

처음에는 DFS를 이용해서 탐색하는 로직을 시도했다.

그러나 너무 많은 재귀 호출로 인한 스택 오버플로우와 시간 초과가 났다.

최소횟수를 찾는것과 최단거리를 찾는것이 똑같다는 생각이 들어 BFS로 변경했다.

더이상 스택 오버플로우는 나지 않았지만 시간 초과가 나는건 똑같았다.

한참을 고민하다 방문 배열과 똑같은 역할을 하는 Set을 추가해서 문제를 해결할 수 있었다.

---

최종 코드

import java.util.*;
class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        answer = bfs(x, y, n);
        return answer;
    }
    
    public int bfs(int x, int y, int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        int depth = 0;

        queue.add(x);

        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                int temp = queue.poll();

                if(temp == y) {
                    return depth;
                }
                
                if(temp * 2 <= y && !set.contains(temp * 2)) {
                    queue.add(temp * 2);
                    set.add(temp * 2);
                }
                if(temp * 2 <= y && !set.contains(temp * 3)) {
                    queue.add(temp * 3);   
                    set.add(temp * 3);
                }
                if(temp * 2 <= y && !set.contains(temp + n)) {
                    queue.add(temp + n);   
                    set.add(temp + n);
                }
            }
            depth++;
        }
        return -1;
    }
}