문제

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

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

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

입력

x : 10
y : 40
n : 5

출력

2

제한 사항

1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

내가 했던 풀이 방법

1. x와 y가 같은 경우 0을 return한다.
2. x에 n을 더해주거나 2를 곱해주거나 3을 곱해주었을 때 모두 y보다 커지는 경우, y로 만들 수 없으므로 -1을 return한다.
3. 1번과 2번이 아닌 경우, queue에 [x, 0]을 추가해준다. 여기서 0은 연산 횟수를 의미한다. 같은 수를 반복하면 연산속도가 느려지고 먼저 같은 수에 도착했던 경우가 연산 횟수가 더 적으므로, set을 이용해 재방문을 방지해준다.
4. queue를 shift를 이용하여 값을 제거해주게 되면 시간 초과가 발생한다. 그러므로 index 변수를 이용해 head부분부터 값을 가져올 수 있도록 해준다.
5. index가 queue의 length보다 작은 경우, queue의 가장 첫 번째 요소를 가져와 current와 count에 저장해준다. current가 y와 같을 경우 count를 return 한다. y와 같지 않고 current를 방문한 적이 없는 경우, visited에 current를 추가해주고, n을 더해준 값, 2를 곱해준 값, 3을 곱해준 값을 count+1을 하여 각각 추가해준다. 이때, 연산된 값이 y를 넘어가는 경우에는 queue에 추가해주지 않는다. 이를 index가 queue.length보다 커질 때(queue를 모두 확인)까지 반복한다.
6. 모든 연산이 끝난 뒤에도 return되지 않았다면 -1을 return 한다.

코드

function solution(x, y, n) {
    var answer = 0;
    if(x===y) return 0;
    else if(x+n>y && x*2>y && x*3>y) return -1;
    else {
        let queue = [[x, 0]];
        let visited = new Set();
        let index = 0;
        
        while(index < queue.length) {
            let [current, count] = queue[index++];
            if(current===y) return count;
            
            if(!visited.has(current)) {
                visited.add(current);
                if(current+n<=y) queue.push([current+n, count+1]);
                if(current*2<=y) queue.push([current*2, count+1]);
                if(current*3<=y) queue.push([current*3, count+1]);
            }
        }
    }
    return -1;
}

회고

DFS로 접근했다가 시간초과... BFS는 구현하기 쉽긴한데 DFS에 비해 뭔가 구현할 때마다 어떻게 해야할지 고민이 되는 것 같다... DFS처럼 반복학습을 안 해서 그런가.. 이 문제는 6번 케이스가 계속 틀렸는데 x와 y가 같은 건 0으로 해주어야 하는 걸 놓쳤다.......... 흠........