백준/DFS_BFS
# 1697 숨바꼭질
bright_code
2021. 4. 10. 23:41
728x90
반응형
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
from collections import deque
n, k = map(int,input().split())
t = [0]*100001
def bfs():
q = deque()
q.append(n)
while q:
a = q.popleft()
if a == k :
print( t[k])
return
for b in ( a-1, a+1, a*2):
if 0<= b < 100001 and not t[b]:
t[b] = t[a] +1
q.append(b)
bfs()
n부터 시작 -> 이동 가능한 칸으로 이동 -> 그 칸에서 다시 센다
한 번 처리된 곳은 또 가지 않는다.
생각해보면 처음 나왔을 때의 값보다 작은 값이 들어오지 않는다.
+) 이걸 dfs 로 접근하면 무한 loop가 나온다.
728x90
반응형