백준 1697 숨바꼭질 - 파이썬

문제.

풀이.

처음에는 그냥 굉장히 쉬울거라 생각하고 풀었는데 런타임 에러도 나고, 44퍼센트에서 틀렸다고 뜨기도해서

뭐가 문제인지 찾는데 시간이 좀 걸렸다.

우선 기본적인 BFS 방식으로 풀면되는데 주의 해야할 점은 찾아야 K가 N보다 작을 수 있다는 점을 간과하고

리스트를 K크기만큼 선언을 하였어서 실패했었고, 크기를 K, N 값중 더 큰 값으로 배열을 선언했다가 44퍼센트에서 틀렸었다.

생각해보니 찾아야할 점이 100000이여도 배열을 100000만큼만 선언하여서는 안된다 x2를 했다가 돌아오는 경우가 있기 때문에 배열 범위를 넉넉하게 잡아줘야한다.

 

소스코드.

import sys
from collections import deque
def BFS(n):
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        for i in range(3):
            if dx[i] == 2:
                nx = x * 2
            else:
                nx = x + dx[i]

            if (0<= nx <idx):
                if matrix[nx] == 0:
                    matrix[nx] = matrix[x] + 1
                    if nx == k:
                        return
                    queue.append(nx)


dx = [1, -1, 2]

n, k = map(int, sys.stdin.readline().split())
idx = 200000
matrix = [0] * idx
matrix[n] = 1
if n == k:
    print(0)
else:
    BFS(n)
    print(matrix[k]-1)