[알고리즘] Java / 백준 / A→B / 16953

[알고리즘] Java / 백준 / A→B / 16953

문제

문제 링크

접근 방식

bfs로 A에서 2를 곱한 값과 오른쪽에 1을 더한 값을 카운트와 함께 배열로 저장해가며 탐색한다.

A에서 cnt만큼 이동한 value 값이 B와 같으면 answer를 cnt+1로 설정하고 bfs를 탈출한다.

만약 value 값이 B보다 크면 continue로 다음 큐를 탐색한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_16953 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		
		long answer = -1;
		
		Queue<long[]> queue = new LinkedList<>();
		queue.add(new long[] {A,0});
		
		while(!queue.isEmpty()) {
			long[] info = queue.poll();
			long value = info[0];
			long cnt = info[1];
			
			if(value>=B) {
				if(value == B) {
					answer = cnt+1;
					break;
				}
				continue;
			} 
			
			queue.add(new long[] {value*2,cnt+1});
			queue.add(new long[] {value*10+1, cnt+1});
			
		}
		
		System.out.println(answer);
	}

}