[백준] 1697번 숨바꼭질 파이썬 코드

코드

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

subin, dongsang = map(int, input().split())
check = [0] * 100001 # 방문체크 및 이동 횟수 기록용

def bfs(x, y):
  queue = deque([x])
  while queue:
    popnum = queue.popleft()
    if popnum == y: return check[popnum] # 뽑은 숫자가 동생이 있는 곳이면 함수 종료
    for i in [popnum + 1, popnum -1, popnum*2]: # for문에 +1 이동, -1 이동, *2 이동 기록  
      if 0<=i<= 100000 and not check[i]: # i 범위를 정해주지 않으면 index error 
        check[i] = check[popnum] + 1     # 방문기록을 체크하지 않으면 메모리초과 에러가 난다
        queue.append(i) 
print(bfs(subin, dongsang))

어떻게 해결해야할지는 떠올랐는데 구현이 오래걸린 문제. 롤드컵 보느라 그런 것도 있다. 처음 내 방식으로는 x+1, x-1, 2*x를 리스트에 넣어 하나씩 뽑아서 확인하는 방식이었다. 그러다보니 이중 for문까지 동원되었다. 그런데 첫 for문에 [x+1, x-1, 2*x를 준 코드를 보고 놀랐다. 이렇게 하면 쉽게 할 수 있는데 왜 어렵게 돌아갔을까... 좀 아쉬운 부분도 있었지만 나아지면 될 일이니까. 열심히 해야겠다.

 

추가

1. 방문 체크에서 에러가 나면 메모리 초과가 난다는 사실을 알았다.

2. 이 문제에서는 왜 최대 범위를 준다는 생각을 안했을까... 0이상인 것만 체크해서 indexerror가 났었다.