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

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

1697번: 숨바꼭질

Problem

 

수빈이와 동생이 숨바꼭질을 하는 중이다. 수빈이와 동생의 위치가 주어졌을때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하여라.

 

조건

• 수빈이의 위치가 X라고 할 때, 수빈이는 2*x,x+1,x-1로 이동할 수 있다.
• 현재 점 N(0≤N≤100,000),동생은 점 K(0≤K≤100,000)에 있다.

SOL)

 

BFS는 최단시간을 알아낼 수 있는 탐색방법 중 하나인걸 잊으면 안된다!! 라고 알려주는 문제이다.

1차원 board에 수빈이와 동생의 위치가 각각 표시되어 있고, board에 도달하면, 기록된 거리를 출력해주면 된다.

from collections import deque

def bfs():
    dq.append(N)
    while dq:
        x = dq.popleft()
        if x ==K:
            print(board[x])
            return
        for nx in (x-1,x+1,2*x):
            if 0<=nx<100001 and not board[nx]:
                dq.append(nx)
                board[nx] = board[x] +1
N,K = map(int,input().split())
dq= deque()
board=[0]*(100001)
bfs()