백준 1697 숨바꼭질 파이썬

1697번: 숨바꼭질 (acmicpc.net)

 

n, k = map(int, input().split())
#최단 경로 찾는 건데 n은 -1, +1, *2 중에 하나 할 수 있다. 

from collections import deque

arr=[0]*(100001)

def bfs(x):

    queue=deque()
    queue.append(x)
    arr[x]=1

    while queue:
        x=queue.popleft()
        nx=[x+1, x-1, x*2]
        if x+1 == k or x-1 == k or x*2==k:
            arr[k]=arr[x]+1
            break
        for i in nx:
            if i>0 and i<len(arr) and arr[i]==0:
                queue.append(i)
                arr[i] = arr[x]+1

    return arr[k]-1

if n==k:
    print(0)
else: 
    print(bfs(n))

 

 

bfs로 풀었다. 

 

주의할 점:

 

1. 이동 횟수 저장하는 배열인 arr의 크기를 처음에는 max(n, k)+1로 설정했었는데

n이 이동하다보면 n이나 k를 넘어설 수도 있어서 len(arr)을 10만1로 바꿨다. 

 

2. n=k인 경우는 이동 횟수가 0으로 출력되도록 따로 설정해야 함. 

 

3. n, k는 0부터 가능하다. 처음에는 n, k가 자연수부터 시작이라고 생각해서 arr의 인덱스 값에서 -1을 하려고 했는데 그럴 필요 없음.