[백준/Python] 1697번 - 숨바꼭질

문제

백준 1697번 - 숨바꼭질

해결 과정

• 수빈이가 동생을 찾을 수 있는 가장 빠른 시간 구하기 -> BFS

시행 착오

• 처음에는 for 문에 if문을 넣어서 동생의 위치(숫자)를 찾았을 때 break을 어디에 걸어야 while문을 빠져나올 지 고민 -> if을 for문 밖으로 빼라..
• 가장 빠른 시간을 어떻게 구할까?
  • cnt에 1씩 더할까? -> 거리를 리스트로 만들어준다.
• i가 무한히 커질 수 있기때문에 범위를 설정해줘야함.
• 방문처리가 되었는지 확인해야한다..

array = [0,0,0,0,5]
if not array[1]:
   print("0이다")
else:
   print("0이 아니다")
# 0이다

풀이

import sys
from collections import deque

n, k = map(int,sys.stdin.readline().split())

# 거리를 저장하는 리스트
dist = [0 for _ in range(100001)]

# BFS 구현    
def bfs(n):
  queue = deque([n])
  while queue:
    v = queue.popleft()
    if v == k:
      print(dist[v])
      break
    for i in v+1,v-1,v*2:
      # i가 범위 내에 있고, i를 방문하지 않았다면
      if 0 <= i <= 100000 and not dist[i]:
        queue.append(i)
        dist[i] = dist[v] + 1

bfs(n)