[백준 16953] A → B

[문제 바로가기]👇

16953번: A → B

 

 

💡풀이💡

예제 입력을 보면 어떻게 연산이 적용되어서 A가 B가 되었는지 확인할 수 있다.

이를 보면 어떤 때는 x2연산된 값을 선택했고, 어떤 때는 1을 수의 가장 오른쪽에 추가한 연산된 값이 선택 되었다는 것을 알 수 있다. 그렇기 때문에 A부터 시작해 연산을 뻗어나가면서 B가 되는지 안 되는지를 확인해야한다.

 

예제 입력1번을 예로 들었을 때 A(2)부터 시작해서 연산을 뻗어나가면 이렇게 된다.

위 그림을 봤을 때 첫번째 연산에서는 4 / 21이 , 두번째 연산에서는 8 / 41 / 42 / 211이 연산한 결과로 나온다. 한 번의 단계를 계산 할 때마다 같은 레벨에서 나온 값들을 모두 연산해줘야 한다. 

 

그래서 같은 너비를 모두 탐색할 수 있는 BFS로 접근했다.

 

 

BFS

queue에 현재 값과 현재의 depth를 같이 저장할 수 있도록 했다.

현재 수가 B와 같으면 depth를 리턴하고, 아니면 x2, 일의 자리에 1추가하기(1을 수의 가장 오른쪽에 추가) 연산을 수행한다. 그리고 그 결과가 B보다 작거나 같으면 queue에 추가하고 이를 반복한다.

 

 

 

전체 코드

package M05_1;

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

public class B16953 {
	static int B;
	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());
		B = Integer.parseInt(st.nextToken());
		
		System.out.println(bfs(A));
		br.close();
	}
	
	static long bfs(int a) {
		ArrayDeque<long[]> q = new ArrayDeque<>();
		q.offer(new long[] {a, 0}); // 현재 수 , depth
		
		while(!q.isEmpty()) {
			long[] cur = q.poll();
			
			// 현재 수가 B이면 현재 depth +1 리턴
			if(cur[0] == B) return cur[1]+1;
			
			// 가능한 연산 2가지
			// x2, 일의 자리에 1추가하기
			long[] move = {cur[0]*2, cur[0]*10+1};
			for(int d=0; d<2; d++) {
				// 연산한 수가 B보다 작거나 같으면 queue에 추가
				if(move[d] <= B) q.offer(new long[] {move[d], cur[1]+1});
			}
		}
		
		// while문이 끝났다면 A로 B를 만들 수 없기 때문에 -1 리턴
		return -1;
	}

}