#223 백준 파이썬 [1697] 숨바꼭질 - BFS

https://www.acmicpc.net/problem/1697

 

Solution

조금 다르게 (도착지 부터 계산) 시도해보려다가, 결국 같은 로직임을 깨달았다. B->A루트로 코드를 짰지만 A->B와 곱셈 나눗셈만 다르다.

A에서 B까지 가장 빠르게 도달하는 방법은, A에서 갈 수 있는 모든 길을 1초 부터 찾는 것이다.

 

예를 들어 5 -> 17로 가는 길을 찾는다고 가정하면

0초에 갈 수 있는 수: 5

1초에 갈 수 있는 모든 수: 4, 6, 10

2초에 갈 수 있는 모든 수(이전 방문 수 제외): 3, 7, 8, 9, 11, 12, 20  

3초에 갈 수 있는 모든 수(이전 방문 수 제외): ...16...

4초에 갈 수 있는 모든 수(이전 방문 수 제외): ...17...

K에 도달하는 최소 값은 dp[K]로 표현하였다.

 

이렇게 전수 조사를 해간다. 하는 방법은 물론 BFS 그래프.

n초에 갈 수 있는 모든 수는 n-1초에 갈 수 있는 모든 수에서 -1 하거나, +1 하거나 *2 한 수다.

도달한 방법이 없거나, 해당 방법이 더 빠를 경우 dp[K]에 n을 넣어준다.

 

Python Code

from collections import deque
N, K = map(int, input().split())

MAX = 100001
dp = [MAX] * MAX #미니멈 값을 구하기 위해 최댓값에서 빼준다
dp[K] = 0 #도착지부터 역순으로 감(의미 없음, 출발지부터도 똑같음)

queue = deque() #큐를 빠르게 해주는 도구
queue.append(K)

while queue:
    num = queue.popleft()
    
    if num == N: #정답 나왔을 경우 출력
        print(dp[num])
        break
        
    if num < MAX-1 and dp[num+1] > dp[num] + 1: #+1 경우
        dp[num+1] = dp[num] + 1
        queue.append(num+1)
        
    if num > 0 and dp[num-1] > dp[num] + 1: #-1 경우
        dp[num-1] = dp[num] + 1
        queue.append(num-1)
        
    if num % 2 == 0: #출발지부터 짠다면 이게 바뀔 것이다. 도착지부터 짰기에 나눠주었다.
        if dp[num // 2] > dp[num] + 1:
            dp[num // 2] = dp[num] + 1
            queue.append(num // 2)