π λ¬Έμ μ΄ν΄
μλΉμ΄λ λμμ -1, +1, *2 λΌλ μΈ κ°μ§μ μ νμ§ μ€ νλλ₯Ό κ³¨λΌ μ΄λνκ² λλ€.
μ’μ°λ‘ μ΄λνλ λ κ°μ§μ μ νμ λμμ 1μ΄ μ© μ¦κ°νμ§λ§ μ΄ λ¬Έμ λ λ€λ₯Έ μ¨λ°κΌμ§ λ¬Έμ μ λ€λ₯΄κ²
*2λ‘ μ΄λνλ μ νμ μκ°μ΄ μ¦κ°νμ§ μλλ€λ νΉμ§μ΄ μλ€.
λλΉ μ°μ νμμ μ ννλ€.
ꡬν μΈμ΄: Python
from collections import deque
def solve():
global n, k, sec
queue = deque()
# μμμ μΈν
queue.append(n)
sec[n] = 0
while queue:
now = queue.popleft()
# μκ°μ΄λ: μκ° μ¦κ° μν¨
if 0 <= 2*now <= 100000:
if sec[2*now] == -1:
sec[2*now] = sec[now]
queue.append(2*now)
# μ’μ°μ΄λ: 1μ΄ μ¦κ°
for next in (now-1, now+1):
if 0 <= next <= 100000:
if sec[next] == -1:
sec[next] = sec[now] + 1
queue.append(next)
n, k = map(int, input().split())
sec = [-1]*100001 # μ΄λ μκ° κΈ°λ‘
solve()
print(sec[k])
'Problem_Solving' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ] λ°±μ€ 2468 μμ μμ / BFS (0) | 2021.01.13 |
---|---|
[BOJ] λ°±μ€ 5014 μ€ννΈλ§ν¬ / BFS (0) | 2021.01.13 |
[BOJ] λ°±μ€ 13913 μ¨λ°κΌμ§ 4 / BFS (0) | 2021.01.12 |
[BOJ] λ°±μ€ 12851 μ¨λ°κΌμ§ 2 / BFS (0) | 2021.01.12 |
[BOJ] λ°±μ€ 1697 μ¨λ°κΌμ§ / BFS (0) | 2021.01.07 |