백준 16953 - A → B

Java

16953 번 - A → B

문제

접근 방법

비슷한 유형의 문제를 푼 기억이 있어 접근하기 쉬웠다.

처음에는 boolean 배열을 사용하여 방문 여부를 확인하려 하였는데, 10^9의 개수를 모두 담기에는 문제의 메모리 제한 조건보다 큰 용량이 필요했다.

하지만 처음 문제 제출에서는 걸리지 않고 한번만에 통과하였지만, 리펙토리 하는 과정에서 방문 여부를 확인하는 배열이 필요가 없다는 것을 깨달았다.
그 이유는, 방문 배열을 쓰는 이유가 BFS에서 한번 방문한 값이 추후에 다시 방문하는 경우를 방지하는 것인데,
문제에서는 2배 그리고 * 10 + 1 만 반복되므로, 계속 값이 커져 재 방문 할 일이 없다.

따라서, 방문 배열을 제거하였다.

또한 * 10 + 1 하는 과정에서 int 자료형의 최대 값을 넘을 수 있으므로 if 조건을 이용하여 넘지 못하도록 하였다.

코드

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

public class Main {
	static int a,b, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());

    	a = stoi(stk.nextToken());
    	b = stoi(stk.nextToken());

    	Queue<int[]> queue = new LinkedList<>();
    	queue.add(new int[] {a,0});

    	int[] q;
    	int curN, cnt, nextN;
    	String strN;
    	while(!queue.isEmpty()) {
    		q = queue.poll();
    		curN = q[0];
    		cnt = q[1];

    		if(curN == b) {
    			result = cnt;
    			break;
    		}

    		// 2를 곱한다
    		nextN = curN * 2;
    		if(nextN <= b)
    			queue.add(new int[] {nextN, cnt + 1});

    		// 1을 수의 가장 오른쪽에 추가한다
    		// 만약 기존 값의 (* 10 + 1)이 int 자료형의 최대 크기를 넘는 것을 방지한다.
    		if(curN > Integer.MAX_VALUE / 10 - 1)
    			continue;
    		nextN = curN * 10 + 1;

    		if(nextN <= b)
    			queue.add(new int[] {nextN, cnt + 1});
    	}

    	if(result != 0)
    		System.out.println(result + 1);
    	else
    		System.out.println(-1);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점