백준, 숨바꼭질, 1697, 파이썬

[유형]

bfs

 

[문제링크]

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

 

[요약]

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

[문제풀이]

import sys
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(dist[x])
            break
        for nx in [x-1,x+1,x*2]:
            if 0<=nx<=max and not dist[nx]:
                dist[nx] = dist[x]+1
                q.append(nx)

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

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-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)
        if 0 <= x*2 <= max and not visited[x*2] :
            count[x*2] = count[x] +1
            visited[x*2] = True
            q.append(x*2)

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