자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.
import java.util.*;
class Solution {
public int solution(int x, int y, int n) {
if(x == y){
return 0;
}
int cnt = 0;
Queue<Integer> q = new LinkedList<>();//BFS탐색을 하기위한 queue
Set<Integer> hs = new HashSet<>();//중복된 값을 확인하기 위한 HasgSet
q.offer(x);//BFS탐색을 하기위한 x값을 넣어줌
while(!q.isEmpty()) {
int size = q.size();
for(int i=0 ; i<size ; i++) {//queue에 들어있는 갯수만큼 탐색을 진행
if(q.peek()==y) {//queue의 현재값이 y값과 같다면 결과값을 return
return cnt;
}
addNode(q.poll(), y, n, hs, q);
//해당 함수에서 x+n, x*2, x*3의 값이 y보다 작고 중복이 아닐경우 queue,HashSet에 추가
}
cnt++;
}
return -1;
}
public static void addNode(int num, int y, int n, Set<Integer> hs, Queue<Integer> q) {
if(num+n <= y && !hs.contains(num+n)) {
hs.add(num+n);
q.offer(num+n);
}
if(num*2 <= y && !hs.contains(num*2)) {
hs.add(num*2);
q.offer(num*2);
}
if(num*3 <= y && !hs.contains(num*3)) {
hs.add(num*3);
q.offer(num*3);
}
return;
}
}