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

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

1697번: 숨바꼭질

 

내 코드

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
board = [0 for i in range(100001)]

def bfs(n):
    q = deque([n])
    while q:
        x = q.popleft()
        if x == k:
            return board[x]
        for nx in (x-1, x+1, 2*x):
            if 0 <= nx <= 100000 and not board[nx]:
                board[nx] = board[x]+1
                q.append(nx)
        
print(bfs(n))

 

인덱스 에러

늘 제출하던 pypy3로 제출하니까 자꾸 인덱스 에러가 떴다. 답은 정상적으로 나오는데 이상해서 찾아보니 인덱스 에러가 나오는 이유는 크게 두 가지였다.

1. 조건문의 and가 값을 처리하는 방식이 순차적이라서
2. 크기를 100000 혹은 1000001 까지로 설정해서

먼저 1번의 경우에는 and 가 앞의 순서부터 처리한다고 한다. A and B일 경우에는 A가 맞고~ 그 다음 B도 맞으면~ 이렇게 처리되는 것이다.

if not board[nx] and 0 <= nx <= 100000 :

그런데 만약 조건문에 이렇게 생겨먹었다면 런타임 에러가 발생한다.

일반적인 bfs 문제 풀 때 등장했던 +1, -1 일 때는 에러가 발생하지 않았다. 하지만 이번 문제는 *2가 있다. 이건 갑자기 수가 커지므로 범위를 벗어나서 있지도 않은 인덱스를 확인하려고 할 수도 있다. 

if 0 <= nx <= 100000 and not board[nx]:

그래서 순서를 이렇게 바꿔주는 것이 필요하다.

2번의 경우에는 마지막 순서인 100001이 될 경우에 런타임이 발생한다. 이런 경우에는 100002로 바꿔주면 해결된다.