백준 / 1697 / 숨바꼭질 (bfs)

from collections import deque

n, k = [int(v) for v in input().split()]
l = k + 2  if n <= k else n+1
graph = [0]* l

q = deque([[n ,0]])
while q:
    x, deph = q.popleft()
    graph[x] = deph
    if x == k:
        # print(list(enumerate(graph)))
        print(deph)
        break

    if x+1 < l and not graph[x+1]:
        graph[x+1] = deph+1
        q.append([x+1, deph+1])
    if x > 0 and not graph[x-1]:
        graph[x-1] = deph+1
        q.append([x-1, deph+1])
    if x *2 < l and not graph[x*2]:
        graph[x*2] = deph+1
        q.append([x*2, deph+1])

bfs로 해결하는데 이 문제에서 주의할 점은 길이이다. 시작 지점이 도착 지점보다 큰 경우 n 값으로 길이를 설정해 줘야한다. 시작 지점이 도착 지점보다 큰 경우는 빼는 경우 밖에 존재하지 않는다. 따라서 n+1 값으로 graph list의 길이를 설정하면 충분하다.

시작 지점이 도착 지점보다 큰 경우를 생각하지 못해서 index error가 계속 났었다.

다른 분들은 대부분 n의 최대 값으로 list 길이를 설정했는데 indexError를 피하기에는 이 방법도 좋아 보인다. 어차피 int list의 경우 메모리가 크지 않으므로... 최대 값이 더 크다면 위 방법으로 하는게 더 효율적일 것이다.