1 분 소요

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())

visited = [False]*200001

def bfs(v):
  queue = deque([v])
  count = 0
  while queue:
    size = len(queue)
    for j in range(size):
      x = queue.popleft()
      visited[x] = True

      if x == k:
        return count

      for i in (x-1,x+1,x*2):
        if 0 <= i <= 100001 and not visited[i]:
          visited[i] = True
          queue.append(i)
    count+=1


print(bfs(n))

»intput

5 17

»output

4

success

image-20220306212418820


🌝 Thinking

[아이디어]

  1. 수빈이가 이동 할 수 있는 곳의 리스트를 값을 모두 False로 초기화 해놓는다.(수빈의 위치 = 리스트의 Index)
  2. 수빈이가 1초 후 움직일 수 있는 곳의 좌표를 모두 방문처리함과 동시에 방문한 값을 Queue에 넣는다.
  3. Queue에서 자료를 하나씩 뽑으며 2번과정을 반복한다.(BFS알고리즘 이용)
  4. 수빈이가 도달하고자는 값이 방문이 되었다면, BFS의 Level을 측정하여 출력한다.



💡 깨달은 점.

  1. 최적 해를 구하는 것을 보고, 바로 DP알고리즘으로 접근을 해서 낭패를 보았다. BFS알고리즘 역시 최적해를 찾아낼 수 있다.

댓글남기기

참고