[백준] 13549: 숨바꼭질3 python 구현 / BFS

문제

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

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

풀이

1. location의 범위를 [0, 100000]으로 설정해주어야 한다.
2. 수빈이와 수빈이 동생은 같은 위치에 있을 수 있다.
   
   • Input: 0 0     / Output: 0
3. Queue에 넣는 순서를 조심하기 - 자세한 설명
   
   • Queue에 넣는 순서가 [2, -1, 1]일 경우에만 올바르게 작동한다.. 사실 해당 코드는 얻어 걸려 답을 맞추는 느낌?
   • 그렇다면 어떻게 푸는 것이 문제가 의도한 방향일까?
     • 다익스트라 알고리즘
     • 0-1 BFS: 가중치가 0인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법
       • 근데 해당 경우에도 *2는 맨 앞에 와야함!
     • * 2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

CODE

from collections import deque

n, k = map(int, input().split())
vst = [0]*(100000+1)

def bfs(cx):
    queue = deque()
    vst[cx] = 1
    queue.append((cx, 0))
    
    move = [2, 1, -1] # queue에 넣는 순서를 조심 !
    while queue:
        x, time = queue.popleft()
        if x == k:
            return 0

        for i in move:
            if i > 1:
                nx = x * 2
                ntime = time
            else:
                if i < 0:
                    nx = x - 1
                else:
                    nx = x + 1
                ntime = time + 1
        
            if nx < 0 or nx > 100000: continue
            if vst[nx]: continue
            
            # 종료 조건 : k에 도달
            if nx == k:
                return ntime
            
            vst[nx] = 1
            if i > 1:
                queue.appendleft((nx, ntime))
            else:        
                queue.append((nx, ntime))


time = bfs(n)
print(time)