[백준, 자바, 16953번] A -> B

풀이

• 해당 문제는 따로 알고리즘이라고 하기엔 뭐가 없었음.
• 그냥 단순히 bfs로 2를 곱한 수와, 해당수에 10을 곱하고 1을 더한 값을 누적하기
• 그리고 같은 값을 계속 반복하면 시간만 낭비하니 Set에 추가하며 확인 후 추가하며 해결

 

import java.io.*;
import java.util.*;
public class _16953 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long[] AB = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        Deque<List<Long>> dq = new ArrayDeque<>();
        dq.add(new ArrayList<>(Arrays.asList(AB[0],1L)));
        Set<Long> s_li = new HashSet<>(Arrays.asList(AB[0]));
        long result = -1;
        while (!dq.isEmpty()) {;
            List<Long> li = dq.pollFirst();
            if (li.get(0)==AB[1]) {
                result = li.get(1);
                break;
            }
            if (li.get(0)*2<=AB[1] && !s_li.contains(li.get(0)*2)) {
                dq.add(new ArrayList<>(Arrays.asList(li.get(0)*2, li.get(1)+1)));
                s_li.add(li.get(0)*2);
            }
            if (li.get(0)*10+1<=AB[1] && !s_li.contains(li.get(0)*10+1)) {
                dq.add(new ArrayList<>(Arrays.asList(li.get(0)*10+1, li.get(1)+1)));
                s_li.add(li.get(0)*10+1);
            }
        }
        System.out.println(result);
    }
}