[프로그래머스, 자바, 154538번] 숫자 변환하기

풀이

• 해당 문제를 BFS와 DP로 해결해봤는데
• 우선 오랜만에 BFS로 해결하다보니
• 방문 체크하는 것에 대한 기본 개념을 잊어버린 나머지 조금 시간이 걸렸음
• 그리고 DP의 경우엔 범위를 어떻게 지정해야 하나 싶었는데 
• 그저 단순하게 x부터 y까지 지정하되
• 탐색하지 않았을 경우에 대한 조건을 두어 체크를 한다면 쉽게 해결이 가능했다.

 

// BFS 풀이

public static int s1(int x, int y, int n) {
    Queue<int[]> li = new LinkedList<>() {{
        add(new int[]{x,0});
    }};
    Set<Integer> visit = new HashSet<>() {{
        add(x);
    }};
    while (!li.isEmpty()) {
        int[] now = li.poll();
        if (now[0] == y) return now[1];
        for (int num: new int[]{now[0]+n,now[0]*2,now[0]*3}) {
            if (num<=y && !visit.contains(num)) {
                visit.add(num);
                li.add(new int[]{num,now[1]+1});
            }
        }
    }
    return -1;
}

 

// DP 풀이

public static int s2(int x, int y, int n) {
    int[] dp = new int[y+1];
    for (int i=x; i<=y; i++) {
        if (i!=x && dp[i]==0) {
            dp[i]=-1;
            continue;
        }

        if (i+n<=y) dp[i+n] = (dp[i+n]==0) ? dp[i]+1 : Math.min(dp[i]+1,dp[i+n]);
        if (i*2<=y) dp[i*2] = (dp[i*2]==0) ? dp[i]+1 : Math.min(dp[i]+1,dp[i*2]);
        if (i*3<=y) dp[i*3] = (dp[i*3]==0) ? dp[i]+1 : Math.min(dp[i]+1,dp[i*3]);
    }
    return dp[y];
}