[JAVA/BFS] 숫자 변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=java#

프로그래머스

 

 

 

해결 포인트

• 최단 거리를 찾는 문제이므로 DFS 보다는 BFS가 적합하다.
• 제시된 대로 x에 연산을 할 경우 시간 초과가 나므로, y에 역으로 연산을 하는 것이 해결책이다.

 

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    
    // BFS에 탑재하기 위한 임시 클래스
    class TmpNum {
        int num;
        int cnt;
        
        TmpNum(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
    
    public int solution(int x, int y, int n) {
        
        int answer = Integer.MAX_VALUE;
        
        // 최소 횟수, 즉 최단 거리를 찾는 문제이므로 BFS 사용
        Queue<TmpNum> bfs = new LinkedList<>();
        bfs.add(new TmpNum(y, 0));
        
        while(!bfs.isEmpty()) {
            TmpNum tn = bfs.poll();
            if(tn.num == x) {
                answer = tn.cnt;
                break;
            }
            else if(tn.cnt == Integer.MAX_VALUE) {
                // -1이 될 수밖에 없음.
                break;
            }
            else {
                // 제시된 세 가지 연산 수행
                // 그런데 그대로 하면 시간초과가 나서, 역으로 실행
                if(tn.num - n >= x) {
                    bfs.add(new TmpNum(tn.num-n, tn.cnt+1));
                }
                if(tn.num%2 == 0 && tn.num/2 >= x) {
                    bfs.add(new TmpNum(tn.num/2, tn.cnt+1));
                }
                if(tn.num%3 == 0 && tn.num/3 >= x) {
                    bfs.add(new TmpNum(tn.num/3, tn.cnt+1));
                }
            }
        }
        
        if(answer == Integer.MAX_VALUE) {
            // 방법이 없으면 -1 리턴
            answer = -1;
        }
        
        return answer;
    }
}