[BOJ] 1697. 숨바꼭질

문제

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

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

from collections import deque
n, k = map(int, input().split())
q = deque([(n, 0)])
INF = 100001
visited = [False] * INF
sec = 0
while q:
  x, sec = q.popleft()
  visited[x] = True

  if x == k: break
  if x - 1 >= 0 and not visited[x - 1]:
    q.append((x - 1, sec + 1))
  if x + 1 < INF and not visited[x + 1]:
    q.append((x + 1, sec + 1))
  if 2 * x < INF and not visited[2 * x]:
    q.append((x * 2, sec + 1))

print(sec)

bfs 알고리즘을 이용한 풀이이다.
여기서 IndexError 조심하자.
뒤로 가는 경우(X - 1)는 이동할 위치가 0이상이어야 한다.

210505 복습

## 숨바꼭질
import heapq
n, k = map(int, input().split())

INF = int(1e9)
visited = [False] * 100001
q = [(0, n)] # second, now
visited[n] = True
 
while q:
  second, now = heapq.heappop(q)
  if now == k:
    print(second)
    break
  
  if now * 2 <= 100000 and not visited[now * 2]:
    visited[now * 2] = True
    heapq.heappush(q, (second + 1, now * 2))
  if now  + 1 <= 100000 and not visited[now + 1]:
    visited[now + 1] = True
    heapq.heappush(q, (second + 1, now + 1))
  if now - 1 >= 0 and not visited[now - 1]:
    visited[now - 1] = True
    heapq.heappush(q, (second + 1, now - 1))

• heapq 라이브러리 이용

이때, 조건문을 통과하고 바로 방문 처리를 하면 시간, 메모리가 반이 줄어든다.