[백준 1697] 숨바꼭질

0. 제목

• 백준 1697 숨바꼭질
• BOJ 1697 숨바꼭질
• 파이썬 1697 숨바꼭질
• Python 1697 숨바꼭질

---

1. 문제

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

1697번: 숨바꼭질

---

2. 풀이

• 현재 위치가 N이라고 할 때 이동가능한 지점은 N + 1, N - 1, 2*N 이다.
• 가장 빠른 시간을 찾기위해 bfs를 사용한다.
• 가장 먼저 현재 위치 좌표를 deque(덱, 큐의 앞과 뒤에서 삽입과 삭제가 가능한 큐)에 넣는다.
• 큐가 빌 때까지 반복한다. 현재 위치를 q의 가장 왼쪽 요소로 갱신하며 탐색을 한다.
• arr라는 배열을 선언하여 해당 지점까지 걸리는 시간을 값으로 가진다. arr[3] = 4 라면 3까지 가는데 4초가 걸린다는 의미이다.
• 현재 위치에서 이동 가능한 값들 중 거리범주 내에 있고 방문하지 않았던 지점이라면 현재 지점까지 걸렸던 시간에서 1을 더해준다.
• 방문한 점을 deque에 append로 추가해준다.
• 현재 위치가 최종 목적지와 같아지게 되면 걸린 시간을 반환해주고 그 값을 출력한다.

---

3. 코드

from collections import deque
 
MAX = 100001
n, k = map(int, input().split())
arr = [0] * MAX
 
def bfs():
    q = deque([n])
    while q:
        now_pos = q.popleft()
        if(now_pos == k):
            return arr[now_pos]
        for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
            if 0 <= next_pos < MAX and not arr[next_pos]:
                arr[next_pos] = arr[now_pos] + 1
                q.append(next_pos)
                
print(bfs())