반응형
문제
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
문제 풀이
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
MAX = (10 ** 5)
def bfs(root, find):
distance = [0] * (MAX+1)
queue = deque([root])
while queue:
x = queue.popleft()
if x == find:
return distance[x]
for nx in [x - 1, x + 1, x * 2]:
if 0 <= nx <= MAX and not distance[nx]:
distance[nx] = distance[x] + 1
queue.append(nx)
result = bfs(n, k)
print(result)728x90
반응형