백준, 숨바꼭질3, 13549, 파이썬

[유형]

bfs

 

[문제링크]

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

 

[요약]

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

[문제풀이]

import sys
sys.setrecursionlimit(10**7)
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()

        if x == k:
            print(count[x])
            break

        if 0 <= x*2 <= max and not visited[x*2] :
            count[x*2] = count[x] 
            visited[x*2] = True
            q.appendleft(x*2)

        if 0 <= x-1 <= max and not visited[x-1] :
            count[x-1] = count[x] + 1
            visited[x-1] = True            
            q.append(x-1)

        if 0 <= x+1 <= max and not visited[x+1] :
            count[x+1] = count[x] + 1
            visited[x+1] = True            
            q.append(x+1)

max = 10**5
count = [0]* (max+1)
visited = [False]* (max+1)
n,k = map(int,input().split())
bfs()