[BFS] 백준 : 16953_A->B

[inseonyun]

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

문제 요구사항 :

• 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
  • 2를 곱한다.
  • 1을 수의 가장 오른쪽에 추가한다.
• A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
• 첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.
• A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

접근 방법 :

• queue에 현재 숫자와 cost를 넣고 문제 조건 연산을 수행하며 값과 cost + 1을 넣으며 수행, 탐색 중 값이 같다면 최솟값과 비교하여 cost가 더 작으면 최솟값 갱신
• 문제에서 주어진 B의 최댓값 안 보고 int형으로 코딩했다 틀렸다.

풀이 순서 :

1. A와 B를 입력 받는다
2. queue에 현재 넘버 A와 cost 0을 넣고 queue가 빌 때까지 BFS 탐색을 수행한다.
3. BFS 수행
   • queue에서 꺼낸 수가 B와 같다면 minimum과 현재 cost를 비교하여 작다면 갱신하도록 한다.
   • 꺼낸 수를 문제의 조건대로 연산하는데 이때, 값이 B 이하라면 queue에 그 값과 cost +1 값을 넣는다.
   • 이와 같은 작업 반복
4. minimum이 MAX 값과 같다면 -1을, 아니라면, minimum을 출력한다.

[inseonyun]

문제 풀이 결과 :