2022.02.13 [백준] (python 파이썬) 숨바꼭질

 

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

1697번: 숨바꼭질

 

 

---

풀이

이 문제는 n점에서 부터 k점까지 이동할 때의 최단거리를 구하는 문제이므로 bfs를 이용했다.

처음 이동할 수 있는 경우를 하나하나 다 따로 작성 후 조건도 따로 했다.

코드를 제출 후 다른사람의 코드를 구글링하다가 이동할 수 있는 경우를 for문의 반복범위로 두고 하면 코드가 짧아지는 것을 알게 되었고 줄여보았다.

from collections import deque
 
n,k=map(int, input().split())
 
arr=[0]*(10**5+1)
 
def bfs(start,end):
    deq=deque()
    deq.append(start)
    arr[start]=1
    while True:
        X=deq.popleft()
        if X==end:
            break
        # X_p=X+1
        # if 0<=X_p<=100_000 and arr[X_p]==0:
        #     deq.append(X_p)
        #     arr[X_p]=arr[X]+1
        # X_m = X - 1
        # if 0 <= X_m <= 100_000 and arr[X_m] == 0:
        #     deq.append(X_m)
        #     arr[X_m] = arr[X] + 1
        # X_2 = X * 2
        # if 0 <= X_2 <= 100_000 and arr[X_2] == 0:
        #     deq.append(X_2)
        #     arr[X_2] = arr[X] + 1
        # 위 주석 처리된 코드를 줄여보자!!
        for nx in (X+1,X-1,X*2):
            if 0<=nx<=10**5 and arr[nx]==0:
                deq.append(nx)
                arr[nx]=arr[X]+1
 
bfs(n,k)
print(arr[k]-1)