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

소스코드

import sys

from collections import deque

input = sys.stdin.readline()

def bfs():

    q = deque()

    q.append(n)

    while q:

        x = q.popleft()

        if x == k:

            print(dist[x])

            break

        for j in (x-1,x+1,x*2):

            if 0<= j <= MAX and not dist[j]:

                dist[j] = dist[x] +1

                q.append(j)

MAX = 100000

n,k = map(int,input.split())

dist = [0] * (MAX+1)

bfs()

알고리즘

BFS를 이용하여 풀 수 있는 문제입니다.

5 17을 예시로 설명을 하자면 

5를 먼저 큐에 삽입합니다.

그리고 5에 관하여 -1, *2, +1 연산을 한 숫자인 4,10,6을 큐에 넣습니다.

이런식으로 쭉 넣다보면 원하는 값을 찾을 수 있게 됩니다.