[Silver I] 숨바꼭질 - 1697

문제 링크

성능 요약

메모리: 35108 KB, 시간: 112 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

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

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

입력

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

출력

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

---

문제 풀이

아이디어

큐에 먼저 들어갔으면 가장 값이 최소임을 생각하자

BFS를 사용하여 graph 배열을 십만+1까지 0으로 초기화하였다. 그러고 bfs 함수를 수빈이의 위치 n부터 돌면서 처음 graph[n] 값은 1로 초기화하고, 큐를 계속 돌면 된다.

여기서 방향값에 순간이동을 하는 경우에는 현재 좌표의 2배 값으로 이동하게 되므로, 방향 배열 dx에서 매번 큐를 돌 때마다 dx[2]값을 큐에서 나온 값인 v로 선언해줘야 한다.

처음에 틀렸습니다가 떠서 최소값을 매번 생각해줘야 하나 하면서 삽질을 했었는데, 알고봤더니 범위를 따질 때 100000 보다 크거나 같으면 고려하지 않게 설계해서 그런거였다. 애초에 배열 크기를 100001로 계산했으므로 nx가 십만이 되어도 고려해줘야 하는건데 생각을 잘 못 했다.

그리고 굳이 최소값을 매번 생각해줄 필요가 없는게, 이미 큐에 k가 처음 들어온 시점이 가장 최소값이기 때문이다. 가장 빠른 방법으로 들어온 건데 굳이 또 고려해줄 이유가 없다.

코드

import sys
from collections import deque

input = sys.stdin.readline
n, k = map(int, input().split())


def bfs(x):
  queue = deque()
  queue.append(x)
  graph[x] = 1
  dx = [-1, 1, 0]
  while queue:
    v = queue.popleft()
    # 2*v 위치로 이동을 위해 dx[2]를 v로 초기화시킨다.
    dx[2] = v
    for i in range(3):
      nx = v + dx[i]
      # 범위를 벗어난 경우 고려 x -> 범위가 십만까지 된다. 100001로 초기화해서
      if nx < 0 or nx > 100000:
        continue
      if graph[nx] == 0:
        graph[nx] = graph[v] + 1
        queue.append(nx)
  # 동생 좌표 k 값을 출력한다.
  return graph[k]


graph = [0] * 100001
print(bfs(n) - 1)