[프로그래머스,Java] Levle2: 숫자 변환하기

 

문제분석

 

딱 보자마자 DP 문제임을 눈치채면 성공

 

근데 필자는 BFS로 풀었다.  

뭔가 BFS가 좀더 효율적인거같아서 햇는데,  결국 빅데이터일수록 DP가 더 빠르더라..

 

 

BFS는  레벨을 기준으로 너비탐색을 한다.

 

필자는 레벨을 연산횟수와 동일하게보고 BFS를 진행했다.

 

같은 연산을 여러번하는걸 막기위해 Boolean체크도 잊지않게 해주면된다.

 

 

전체 풀이

import java.util.*;
class Solution {
 
    public int solution(int x, int y, int n) {
        int answer = 0;
        
        if(x==y){
            return 0;
        }
 
        boolean[] visited = new boolean[y+1];
 
        Queue<int[]> que = new LinkedList<>();
 
        que.add(new int[]{x,0});
 
        while(!que.isEmpty()){
            int[] q =que.poll();
            visited[q[0]]=true;
            if(q[0]+n==y||q[0]*2==y||q[0]*3==y){
                return q[1]+1;
            }
 
            if(q[0]*3<=y&&!visited[q[0]*3]) que.add(new int[]{q[0]*3,q[1]+1});
            if(q[0]*2<=y&&!visited[q[0]*2]) que.add(new int[]{q[0]*2,q[1]+1});
            if(q[0]+n<=y&&!visited[q[0]+n]) que.add(new int[]{q[0]+n,q[1]+1});
 
        }
 
        return -1;
    }
}