문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
예제 입출력
접근 및 코드
이 문제의 접근은 다음과 같다.
1. 문제 판단
위의 그림을 보면 각 숫자를 노드로 생각하면 마치 그래프같다.
문제를 보면 한 숫자에서 다음 숫자로 갈수 있는 경우는 2를 곱하는 경우와 1을 수의 가장 오른쪽에 추가하는 경우다.
즉, 숫자를 노드로 보고 인접 노드를 두 가지 연산을 하는 경우로 생각하면 그래프 생각할수가 있게 된다.
2. 그래프탐색
이 문제는 미리 그래프를 만들고 그것을 탐색하는 것이 아니므로 바로 탐색해보겠다.
위에서 그래프로 생각했으니 바로 입력으로 주어진 첫번째값을 시작노드로 해서 bfs그래프를 그리면서 탐색을 한다.
각 노드는 연산횟수 저장을 위해서 count하는 값을 저장해줘야 한다.
bfs탐색을 하면서 두번째로 주어진 수와 동일한 노드가 나오면 그 즉시 반복문을 종료 하고 count값을 출력해준다.
bfs탐색이고 큐에서 꺼내는 것이므로 먼저 나온것이 연산횟수가 적은 노드가 된다.
만약 반복문이 끝날때까지 탐색을 했는데도 목표하는 값을 가진 노드가 없다면, 도달할수 없다고 생각하고 -1을 출력해준다.
이때 주의해줘야 되는것이, 문제에서 주어진 최대값이 10^9이다.
bfs로 탐색하면서 인접노드를 추가할때 이 값을 넘어가면 추가하지 않도록 해야된다.
그렇지 않으면 도달할수 없는 값이었다면, 끝없이 증가해서 시간초과가 날수도 있다.
코드는 다음과 같다.
import sys
from collections import deque
'''입력'''
a,b = sys.stdin.readline().split()
#메모리 초과가 안나도록
max = 10**9
#bfs정의
def bfs(start_node:str,end_node:str):
visited = dict()
need_visited = deque(list())
need_visited.append([start_node,1])
visited[start_node] = 1
while need_visited:
current_node, current_count = need_visited.popleft()
if current_node == end_node:
return current_count
next_node_list = [str(int(current_node)*2),current_node+'1']
for next_node in next_node_list:
if next_node not in visited and int(next_node) <= max:
visited[next_node] = current_count + 1
need_visited.append([next_node,current_count+1])
return -1
print(bfs(a,b))결과
