[백준/자바] 16953번: A → B

문제

https://www.acmicpc.net/problem/16953

풀이

• 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

1. 2를 곱한다.
2. 1을 수의 가장 오른쪽에 추가한다.

• A를 B로 바꾸는데 필요한 연산의 최솟값 출력

BFS 탐색을 활용해 문제를 해결할 수 있습니다.
queue에 (현재 값, 연산 횟수)를 집어넣어 최소 연산 횟수를 찾아낼 수 있습니다.

	private static long bfs() { 
		Queue<long[]> queue = new ArrayDeque<>();
		queue.add(new long[] {a, 1});

• A와 B의 범위는 최대 10^9입니다.
• 연산을 진행할 때, node의 값 * 10 + 1이란 연산을 진행하므로, 최악의 경우 node의 값이 10^9일 때, * 10 + 1 연산을 진행하면 int 범위를 초과하므로 long으로 탐색을 진행했습니다.

		while (!queue.isEmpty()) {
			long[] cur = queue.poll();
			long node = cur[0]; // 현재 값
			long cnt = cur[1]; // 연산 횟수
			
			if (node == b) return cnt; // b가 됐다면 종료
			
			if (node * 2 <= b) { // 2를 곱한 값이 b 이하라면 큐에 삽입
				queue.add(new long[] {node * 2, cnt + 1});
			}
			
			if (node * 10 + 1 <= b) { // 뒤에 1을 붙인 연산이 b 이하라면 큐에 삽입
				queue.add(new long[] {node * 10 + 1, cnt + 1});
			}
		}
		
		return -1; // 리턴하지 못했다면 만들 수 없는 수이므로 -1 리턴
	}

• 진행할 수 있는 연산을 모두 진행하고 기저조건에 걸리지 않아 while문이 종료되었다면, -1을 리턴해 주었습니다.

코드

import java.util.*;
import java.io.*;

public class Main_16953 {
	static long a, b;
	
	private static long bfs() {
		Queue<long[]> queue = new ArrayDeque<>();
		queue.add(new long[] {a, 1});
		
		while (!queue.isEmpty()) {
			long[] cur = queue.poll();
			long node = cur[0];
			long cnt = cur[1];
			
			if (node == b) return cnt;
			
			if (node * 2 <= b) {
				queue.add(new long[] {node * 2, cnt + 1});
			}
			
			if (node * 10 + 1 <= b) {
				queue.add(new long[] {node * 10 + 1, cnt + 1});
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		a = Long.parseLong(st.nextToken());
		b = Long.parseLong(st.nextToken());
		System.out.println(bfs());
	}

}