[백준] 1697 파이썬(python) : 숨바꼭질 - (★)

1697번 : 숨바꼭질

 

 

 

from collections import deque
n, k = map(int, input().split())
MAX = 10**5 #1
distance = [0] * (MAX + 1) #2

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        if x == k: #3
            print(distance[x])
            break
        for nx in (x-1, x+1, 2*x): #4
            if 0 <= nx <= MAX and distance[nx] == 0: #5
                distance[nx] = distance[x] + 1
                q.append(nx)
bfs()

 

#1 : n과 k의 최대 범위

#2 : n = 100,000일 수 있으므로 (MAX+1)로 지정

#3 : 반복문 탈출조건

#4 : nx는 x-1, x+1, 2*x 각각 하나씩 값을 가짐. 예제에서 입력값 n=5이니까 nx는 4, 6, 10이 되어 반복문을 수행

#5 : nx가 n의 범위를 넘어가지 않고 처음 방문한 곳이면 새로운 장소에서의 시간갱신하고 q에 nx추가

 

bfs를 그래프 문제가 아니어도 이렇게 활용할 수 있다는것을 새로 배울 수 있는 문제였다.