본문 바로가기

취준/백준

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

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

 

1697번: 숨바꼭질

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

www.acmicpc.net

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])