숨바꼭질 실버 1

해당 문제를 보고 처음에는 수학적으로만 접근하면 된다고 생각했다.

근데 공식을 생각할 수록, 난잡하게 짜여지길래 bfs로 풀어야한다고 생각했다.

N과 K의 값의 조건은 0과 100,000 사이라고만 주어졌다, 즉, N이 K보다 클수도, 작을 수도 있는 상황이라는 것도 참고해서 그래프로 풀어야겠다는 생각을 했다.

bfs에서 무한루프를 돌지 않게 하기 위한 조건문을 정한다.

1. 새로 탐색하려는 점의 좌표의 값이 업데이트가 되었다면 새로 탐색해야 하는 노드로 간주해야 한다.
   • 이전까지 어떤 가중치가 들어오든, 더 작은 가중치가 들어오면 이 노드도 탐색대상으로 생각해야 한다.
2. 그리고 1번에서 언급한 점의 좌표가 target (K) 좌표라면 더 이상의 탐색은 하지 않는다. 우리가 원하는 K좌표의 최단 count 수를 구해야하기 때문이다.

조건문만 잘 선택했다면 아래와 같이 구현할 수 있다.

import sys 
from collections import deque 
N,K = list(map(int, sys.stdin.readline().strip().split()))
MAXCOUNT = 100001
current_map = [MAXCOUNT] * MAXCOUNT
def bfs(start, target):
    current = deque([start])
    current_map[start] = 0
    options = [-1,1,2]
    while current:
        node = current.popleft()
        for option in options:
            examine_node = option+node if option!=2 else option*node 
            if 0<= examine_node < MAXCOUNT:
                temp, current_map[examine_node] = current_map[examine_node], min(current_map[node]+1, current_map[examine_node])
                if temp != current_map[examine_node] and examine_node!=target:
                    current.append(examine_node)
bfs(N,K)
print(current_map[K])