[백준-1697] 숨바꼭질

문제

링크

코드

# bfs

import sys
from collections import deque
sys.setrecursionlimit(1000000)

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

visited = [0] * 200000

queue = deque([n])
while queue :
    n = queue.popleft()
    if n == k :
        print(visited[n])
        break
    con = [n-1, n+1, n*2]
    for c in con :
        if 0 <= c <= 100000 and visited[c] == 0 :
            queue.append(c)
            visited[c] = visited[n] + 1

풀이

문제에서 수빈이가 현재 위치가 x일 때, 1초에 x-1, x+1, x*2씩 이동한다고 했다.

큐에 제일 먼저 수빈이의 현재 위치를 넣었고, 수빈이의 현재 위치인 n와 동생의 위치인 k가 같을 때까지 진행했다.

만약 같지 않다면 수빈이가 이동할 수 있는 조건인 x-1, x+1, x*2를 통해서 좌표를 이동했고,
이때 조건을 이용한 값이 0보다 크거나 같고, 100000보다 작거나 같아야 하며, 방문하지 않아야 한다.
이 조건을 다 만족하면 큐에 넣고, 이전 값이 몇 번째로 방문되었는지 확인하고 그 수에 +1해주면 된다.

• 정리

1. 현재 값 큐에 넣기
2. 동생 값과 똑같은지 확인.
   2-1. 똑같다면 완료
3. 같지 않다면 조건을 통해 이동하기.
   3-1. 큐에 넣고 몇 번째로 방문했는지 저장하기
4. 2번으로 돌아가기