[백준] 1697. 숨바꼭질 파이썬 풀이

백준 1697 숨바꼭질

풀이

• 탐색을 하며 타겟이 되는 값을 찾는 가장 최솟값을 찾아야하기 때문에 BFS로 접근을 했습니다.
• 문제에서 입력으로 주어지는 n, k 값의 범위를 지정해주었기 때문에 이를 활용하여 조건을 걸어주었습니다.
• 다음 레벨로 탐색을 할 때의 시점을 문제를 기준으로는 1초가 지난 것이라고 판단하고 이를 판단하기 위해서 distance 배열을 생성하였습니다. 이 배열은 이 전의 값에서 +1을 수행하게 되며 이 배열의 값으로 몇초가 지난건지 확인할 수 있습니다.

from collections import deque  
import sys  

sys.stdin = open("1697_숨바꼭질_input.txt", "r")  
n, k = map(int, sys.stdin.readline().split())  
max = 100000  
distance = [0] * (max+1)  


def bfs():  
    queue = deque()  
    queue.append(n)  

    while queue:  
        tmp = queue.popleft()  
        if tmp == k:  
            print(distance[tmp])  
            break  
        else:  
            for i in (tmp-1, tmp+1, 2*tmp):  
                if (0 <= i <= max) and (distance[i] == 0):  
                    distance[i] = distance[tmp] + 1  
                    queue.append(i)  


bfs()