#Algorithm
문제 번호
1697번 숨바꼭질(S1)
알고리즘 + 이론
BFS + DP BFS 생각이 안 나서 그냥 박치기로햇다가 이틀 동안 풀고 답 봣습니다..
정답 코드
# 1697번 숨바꼭질
# 1초에 뒤로 한 칸 앞으로 한 칸 or 2배이니
# 일단 멀 때는 2배가 당연히 가장 빠르다
# 음 일단 16을 만드려면 그 반인 8 가장 빠르게 만들고
# 8을 만드려면 4를 빨리 만들어야하고
# 17을 만드려면 8이나 9가 가장 빨리 만들어지고
# 99 100 50 25 26 13 14 7 8 9 10
# 99 98 49 48 24 12 6 7 8 9 10
# 99 100 50 25 24 12 11 10
# 9 10 5
# 8 4 5
# 7 8 4 5
# 7 6 5
# 8 7 6 5
# N, K = map(int,input().split())
# K2 = K
# result = []
# time_p = 0
# time_m = 0
# while True:
# if K == N:
# result.append(time_p)
# break
# if 0 < K-N < 3:
# K -= 1
# time_p += 1
# elif K%2 == 0 and K > N:
# K /= 2
# time_p += 1
# elif K%2 == 1 and K > N:
# K += 1
# time_p += 1
# else:
# K += 1
# time_p += 1
# while True:
# if K2 == N:
# result.append(time_m)
# break
# if 0 < K2-N < 3:
# K2 -= 1
# time_m += 1
# elif K2%2 == 0 and K2 > N:
# K2 /= 2
# time_m += 1
# elif K2%2 == 1 and K2 > N:
# K2 -= 1
# time_m += 1
# else:
# K2 += 1
# time_m += 1
# print(min(result))
from collections import deque
N, K = map(int, input().split())
MAX = 100000
dist = [-1] * (MAX + 1)
q = deque([N])
dist[N] = 0
while q:
x = q.popleft()
if x == K:
print(dist[x])
break
for nx in (x - 1, x + 1, x * 2):
if 0 <= nx <= MAX and dist[nx] == -1:
dist[nx] = dist[x] + 1
q.append(nx)
느낀점 & 피드백
BFS DFS 훈련도 좀 해야할듯
이 글이 도움이 되셨나요?