취준/백준
[백준][Python][1697][BFS] 숨바꼭질
puff
2020. 3. 2. 09:11
문제 : 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])