💡 막힌부분

기존의 숨바꼭질과 다른 점은 2배로 이동할 때는 가중치가 0이라는 것이다. 그래서 그냥 graph[nx] = graph[x]+1부분을 graph[nx]=graph[x]로 처리하면 똑같은 것 아닌가하고 제출했는데 틀렸다.

💡풀이방법

틀린 이유는 for문에서의 순서였다. 이 문제에는 3가지의 경우가 있다. 즉 for문을 통해 3가지 경우를 순회해야하는데, 그 순서가 이 문제에서는 굉장히 중요하다.

가장 먼저 우리가 찾고자 하는 것은 최솟값임을 인지해야 한다. 즉, 2배로 이동하는 경우 그래프의 가중치가 0이기 때문에 2배로 이동하는 경우를 먼저 처리하고 그 뒤에 +1과 -1인 상황을 보는 것이다.

그렇다면 +1과 -1의 순서는 어떻게 결정해야 할까?
한가지 예시를 통해 알 수 있다. 만약 -1이 먼저 나오면 4에서 6으로 이동할 때 4 -> 3 -> 6으로 결과값이 1이 나온다. +1이 먼저 나오면 4 -> 5 -> 6이 되기 때문에 결과값이 2가 나온다. 따라서 -1을 먼저 고려해주어야 한다.

💡 0-1 BFS

우리가 bfs나 dfs를 사용할 때 전제 조건은 가중치가 같은 그래프에 적용한다는 것이다. 이 문제에서는 0과 1이라는 다른 가중치가 적용되기 때문에 다른 최단 경로 알고리즘인 다익스트라 알고리즘을 사용해야 하는데, 다익스트라 알고리즘의 시간 복잡도는 O(ElogE) 혹은 O(ElogV)이다. 하지만 이 문제처럼 가중치가 0과 1로 이루어져있다면 0-1 BFS를 사용할 수 있다.

0-1 BFS는 시간 복잡도가 O(V+E)이다. 논리적인 구조는 bfs와 같지만 큐(queue)가 아닌 덱(deque)을 이용하는 것이다. 가중치 값이 작은 0은 덱의 front에 append하고 가중치 값이 큰 1은 덱의 rear에 append하는 것이다. 이런식으로 bfs를 반복하다보면 front에 있는 것을 pop해서 사용하므로 가중치가 0인 부분이 먼저 처리가 되고 값이 더 작으면 최솟값으로 갱신하면 된다.
참고 블로그

📝소스코드

import sys
input = sys.stdin.readline
from collections import deque

N, K = map(int, input().split())
max = 10**5
graph = [0]*(max+1)
visited = [False]*(max+1)
queue = deque()

def bfs(N):
    graph[N] = 1
    visited[N] = True
    queue.append(N)
    while queue:
        x = queue.popleft()
        if x==K:
            print(graph[x]-1)
            return
        for nx in (2*x, x-1, x+1):
            if 0<=nx<=max and visited[nx] == False:
                if nx==x*2:
                    graph[nx] = graph[x]
                    visited[nx] = True
                else:
                    graph[nx] = graph[x]+1
                    visited[nx] = True
                queue.append(nx)

bfs(N)