[백준][Python][1697][BFS] 숨바꼭질

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

1697번: 숨바꼭질

BFS 문제다.

 

위치를 l이라 할때, l-1, l+1, 2*l 을 각각 bfs로 탐색하면 된다.

이 때, BFS에서 중요한 중복 확인을 꼭 해야한다(이 코드에서는 v = dict() 딕셔너리를 이용하여 확인한다.)

또한, 0-100000 범위를 넘지않게 한다.

 

숨바꼭질 2,3,4와 달리 다른 조건이 없으니 이걸로 끝낼 수 있다.

 

import sys
from collections import deque

d = dict()
v = dict()
ret = 1000000000000

n,k = [int(i) for i in sys.stdin.readline().rstrip().split()]

def bfs(n,k):
    global ret,d

    q = deque()
    q.append(n)
    d[n] = 0

    while q:
        l = q.popleft()
        if l in d:
            pass
        if l==k:
            break
        for loc in [l-1,l+1,2*l]:
            if loc not in d and 0<=loc <= 100001:
                d[loc] = d[l]+1
                q.append(loc)

bfs(n,k)
print(d[k])