[백준 1697번] 숨바꼭질 - python

문제 링크

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

풀이 

- bfs 문제

- 큐에 방문한 위치와 몇초에 방문했는지 기록 

- 위치를 이동했을 때마다 x+1, x-1, x*2에 대하여 범위에 해당하고 방문하지 않았으면 큐에 삽입하는 과정 반복

- 동생이 있는 위치에 도착했을 때 몇초가 걸렸는지 출력  

from collections import deque 

n, k = map(int,input().split())

q = deque()
q.append((n,0))

# 방문 표시 
visited = [False] * 100001
visited[n] = True

while q:
  x, s = q.popleft()
  
  if x == k:
    print(s)
    break
  else:
    for i in (x-1, x+1, x*2):
      if 0 <= i <= 100000 and not visited[i]:
        q.append((i,s+1))
        visited[i] = True