백준 16953 - A -> B

[문제 바로가기]

 

1. 유형

BFS

2. 풀이

뒤에 1이 붙는 경우, 2를 곱하는 경우를 모두 탐색해 줍니다.

2차원 배열 BFS에서 4방향을 완전 탐색을 하는 경우와 비슷합니다.

 

여기서 주의할 점은 인풋값이 십억이므로, 뒤에 1을 붙이는 경우는 int타입을 초과할 가능성이 있습니다.

그래서 long타입을 사용합니다.

3. 코드

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

public class Main{
	static int N, M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		bfs();
	}
	static void bfs() {
		Queue<long[]> q = new LinkedList<>();
		boolean visit[] = new boolean[M+1];
		visit[N]=true;
		q.add(new long[] {N, 1});
		long MIN = -1;
		while(!q.isEmpty()) {
			long cur[] = q.poll();
			if(cur[0]==M) {
				MIN = cur[1];
				break;
			}
			long val = cur[0]*2;
			if(val<=M) {
				q.add(new long[] {val, cur[1]+1});
			}
			val = (cur[0]*10)+1;
			if(val<=M) {
				q.add(new long[] {val, cur[1]+1});
			}
		}
		System.out.println(MIN);
	}
	static int stoi(String s) {	
		return Integer.valueOf(s);
	}
}