[Baekjoon] 16953_A → B

Silver II

문제(출처: https://www.acmicpc.net/problem/16953)

---

<A -> B>

 

문제 풀이

 

bfs를 활용하여 A를 B로 바꾸는데 필요한 연산의 최솟값을 구한다.

 

 - my solution (Java)

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

public class _16953_ { // A -> B

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		long A=Integer.parseInt(st.nextToken());
		long B=Integer.parseInt(st.nextToken());
		
		Queue<long[]>queue=new LinkedList<>();
		queue.add(new long[] {A,(long) 0});

		long result=0;
		
		while(!queue.isEmpty()) {
			long temp[]=queue.poll();
			long num=temp[0]*2; // 2를 곱한다
			if(num==B) {
				result=temp[1]+1;
				break;
			}
			if(num<B) queue.add(new long[] {num, temp[1]+1});
			num=temp[0]*10+1; // 1을 수의 가장 오른쪽에 추가한다
			if(num==B) {
				result=temp[1]+1;
				break;
			}
			if(num<B) queue.add(new long[] {num, temp[1]+1});
		}
		if(result==0) System.out.println(-1);
		else System.out.println(result+1);
	}
}

 

•  Main
  • A와 B 입력
  • Queue에 [정수, 필요한 연산의 수] 배열을 넣어준다.
  • queue가 빌 때까지 반복한다 -> queue에서 뽑은 값을 2배 한 후 B값과 같지 않다면 queue에 넣어준다. 1을 수의 가장 오른쪽에 추가하는 것은 queue에서 뽑은 값에 10을 곱한 후 1을 더해주면 된다. 그 값이 마찬가지로 B와 같지 않다면 queue에 넣어줌으로써 반복한다. 만약 B와 같다면 바로 종료해준다. (바뀐 값이 B와 같지 않을 때는 B보다 값이 작을 때 queue에 넣어주는 조건을 추가하였다 -> B보다 크면 어떤 연산을 해도 B로 만들 수 없기 때문이다. )
  • result 값이 초기값인 0과 같다면 B로 만들 수 없다는 뜻이므로 -1을 출력하고 0이 아니라면 result 값을 출력해준다.

---

생각🤔

 

처음에 틀린 이유는 간단했다. 범위 조건을 보지 않아 int를 썼기 때문이었다. 이걸 또 못 찾고...

두 번째는 블로그를 작성하다가 필요 없는 코드를 발견하여 수정하였더니 시간이 거의 절반으로 줄었다. ㅇ_<

---