[백준/Python] 13549 - 숨바꼭질 3

문제

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

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

입력

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

출력

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

풀이 과정
처음에는 문제를 읽었을 때 이거 dp네ㅋ 라고 생각하고 풀었다
근데 문제를 풀다보니 이미 지나온 위치에 대해서도 계속 갱신을 해줘야하는 것 같다는 생각이 들어 dp가 아닌 것 같다고 생각했다
그래서 찾아보니 0-1 bfs라는 알고리즘을 활용하는 문제였다
0-1bfs는 처음 들어보는 알고리즘이어서 다익스트라부터 다시 정리했다

0-1 BFS

0-1 BFS는 다익스트라와 BFS가 합쳐진 알고리즘이지만 가중치가 0,1만 존재할 때 효율적인 알고리즘이다
다익스트라는 최단 경로를 갖는 노드를 우선적으로 처리하며 최단 경로를 찾아나가는 알고리즘이고 bfs는 큐를 활용해 모든 노드를 순회한다
0-1BFS에서는 다익스트라처럼 가중치가 0인 노드를 큐의 맨 앞에 삽입하고 가중치가 1인 경우에는 본래의 bfs처럼 큐의 맨 뒤에 삽입하여 최단 경로를 찾는다

원래의 다익스트라나 bfs는 인접 노드를 방문하지만 문제에서는 X-1, X+1, 2*X 의 세 가지 경로를 방문해야한다
그 중에서도 2*X는 가중치가 0이기 때문에 빠른 탐색을 위해 큐의 맨 앞에 삽입해줘야하고 X-1, X+1은 일반 bfs 처럼 큐의 맨 뒤에 삽입하면 된다
그러나 많은 경우에서 X-1(1칸 뒤에서 X로 오기)가 X+1(1칸 앞에서 X로 오기)보다는 경로값이 작을 것이기 때문에 X-1을 먼저 처리해주는 것이 필요하다

정답 코드

import sys
from collections import deque

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

grid = [0] * 100001
visited = [False] * 100001

q = deque()
q.append(n)
visited[n] = True

while q:
    x = q.popleft()
    if x == k:
        print(grid[k])
        break
    for nx in [x*2, x-1, x+1]:
        if 0 <= nx <= 100000 and not visited[nx]:
            if nx == x*2 and nx != 0:
                grid[nx] = grid[x]
                q.appendleft(nx)
            else:
                grid[nx] = grid[x]+1
                q.append(nx)
            visited[nx] = True