문제
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
입력 예시 1
2 162출력 예시 1
5문제 이해
백준의 1697번 숨바꼭질 문제와 비슷하다.
이 문제는 두 가지 경우를 queue에 넣고 BFS를 돌리면서 값이 B가 되면 그때의 횟수를 출력하면 된다. 2*x가 B를 넘지 않으면 그 값을 큐에 넣고, int(str(x)+"1")가 B보다 크지 않으면 그 값을 큐에 넣어주면 된다. BFS이기 때문에 출력되는 값은 가장 먼저 도달한 최솟값이다.
처음 이 문제를 풀었을때는 숨바꼭질을 풀었던 풀이가 생각이 났다. 그 문제도 visited를 사용했었다. 그렇게 해서 중복을 피하기 위함이었다. 그래서 이 문제도 비슷하게 visited를 사용하려고 했는데 값의 크기 제한이 10억이다. 보통 DFS/BFS로 문제를 풀때 인접행렬을 사용할때는, 즉, N*N의 행렬을 사용할때는 N의 값이 1,000이하여야 한다. 그외에는 인접 리스트를 이용한다. 인접행렬을 사용하려면 행렬의 크기가 천만이하여야 한다. 그래서 이 문제는 visited를 사용할 수가 없다.
여기서 생각해봐야 할 것이 있다. 그러면 1697번 문제는 왜 visited를 사용했어야 했을까. 내 생각에 그 이유는 뒤로 가는 경우가 있기 때문이다. 숨바꼭질 문제는 현재 값에서 앞으로 가는 경우만 다루는 게 아니라 뒤로 가는 경우도 있다. 그래서 재방문을 방지해야해서 visited를 사용한 것이다. 하지만 이번 문제는 앞으로만 나아가기 때문에 굳이 visited는 필요 없는 것 같다.
여담인데 이 문제는 원래 골드5 난이도 였다가 실버1이었다가 실버2가 된 것 같다.
정답 코드
# 백준 16953번 A -> B
# 읽기 효율화
import sys
input = sys.stdin.readline
from collections import deque
def BFS(x, times):
global matrix
queue = deque()
queue.append((x, times))
while queue:
x, times = queue.popleft()
if x == B:
print(times)
return
if (x * 2) <= B:
queue.append((x*2, times+1))
if int(str(x) + "1") <= B:
queue.append((int(str(x) + "1"), times+1))
print(-1) # B값에 도달하지 못하는 경우
# 0. 입력 및 초기화
A, B = map(int, input().split())
# 1. BFS호출
BFS(A, 1) # x좌표, 횟수
# 처음 값도 횟수로 카운트 하기 때문에 1을 넣어준다수정 코드
# 백준 16953번 A -> B
# 읽기 효율화
import sys
input = sys.stdin.readline
from collections import deque
def BFS(x, times):
global matrix
queue = deque()
queue.append((x, times))
while queue:
x, times = queue.popleft()
if x == B:
print(times)
return
for nx in [x*2, int(str(x) + "1")]:
if nx <= B:
queue.append((nx, times + 1))
print(-1) # B값에 도달하지 못하는 경우
# 0. 입력 및 초기화
A, B = map(int, input().split())
# 1. BFS호출
BFS(A, 1) # x좌표, 횟수
# 처음 값도 횟수로 카운트 하기 때문에 1을 넣어준다BFS함수 안에 for반복문을 추가해서 좀 더 깔끔하게 수정했다.
