숨바꼭질 3

문제

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

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

풀이

N과 K가 입력되면 총 세가지 방법이 있다.
1. 2배 (count +0)
2. +1 (count +1)
3. -1 (count -1)

BFS 를 이용해 최단거리를 구하는 문제이다.
최단 거리 일때는 다익스트라 알고리즘을 이용하는 것이 좋다
heapq를 까먹었기 때문에 이용은 못했다..
그래서 시간이 좀 더 소요됐을듯..

,K = map(int,input().split())
INF = 1000001

def Bfs():
  visited = [INF]*(INF+1)
  Q = deque()
  Q.append([N,0])  # node,count
  
  while Q:
    node,count = Q.popleft()
    if visited[node] >count:
      visited[node] = count
    double = node*2
    plus = node+1
    minus = node-1
    
    if 0<=double<INF :
      if visited[double] > count:
        Q.append([double,count])
    
    if 0<=plus < INF : 
      if visited[plus] > count+1:
        Q.append([plus,count+1])

    if 0<=minus < INF : 
      if visited[minus] > count+1:
        Q.append([minus,count+1])

  print(visited[K])
Bfs()

한줄로 이어진

원래는 모든 번호에 무한대로 시작하는 경로수가 있었다 .
만일 3에서 시작한 경우라면 갈 수 있는 노드가 2,4,6이다.
3에서 시작했기 때문에 3의 count 는 0이고 2,4는 1 6은 0이 들어가게 된다.
이 값은 그냥 들어가는 게 아니라 원래의 visted의 값과 비교해서 더 작을 경우에만 들어가게 된다

2에서 시작한 경로는 1,3,4 로 갈 수 있는데,
1은 count가 2 여서 visted로 적용되지만, 3,4는 visted보다 count가 크거나 같다.
같을 경우는 굳이 바꿔줄 필요가 없기 때문에 적용하지 않는다.
count 가 더 클경우는 visted가 작을 경우에서 출발한 count보다 무조건 크게 되기 때문에 적용하지 않는다. => 중복 방지용

heapq를 적용시켰다면, 이 count로 정렬이 되기 때문에 전체를 다 계산하지 않고, K의 visted만 구해도 되기 때문에 더 빨리 계산이 가능했을듯 싶다.