[백준/13549/파이썬] 숨바꼭질 3

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

13549번: 숨바꼭질 3

Problem

• 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
• 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

 

조건

• 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

SOL

이 문제도, 특정 조건에 따라서, deque의 흐름을 조절하는 문제이다. "0"초가 걸리는 텔레포트가 빠르므로, 무적권 텔레포트를 먼저 생각해주는 방식으로 구현하면 된다.

하지만, 이게 생각보다 딱 직관적으로 가는건 아니고, 이 deque의 흐름을 이해하는게 중요한거 같다.

 

문제의 input 예시처럼, 5 17 인 경우를 보자.

 

Flow 1.

x= 5, dq=[10,6,4]

Flow 2.

x= 10, dq = [20,6,4,11,9]

Flow 3.

x= 20, dq= [40,6,4,11,9,19,21]

Flow 4.

x= 40, dq=[80,6,4,11,9,19,21,41,39] 

.....

물론, 방문체크를 해주기 때문에, passing되는 경우가 마지막에 갈수록 많아서 연산을 생각보다는 많이 안하겠지만, 

그래도, 18이라는 숫자에 도달하기 위해서는 많은 연산을 거쳐야한다.  우리가 생각하기에는 "2초"밖에 걸리지 않아 보이지만, 컴퓨터의 내부적으로는 "2"번만에 도달하지 않는다.

 

그래프 문제를 풀때, 이 점에 대해서 이해를 잘해야한다.

 

import sys
from collections import deque

input= sys.stdin.readline
N,K=map(int,input().split())
board=[0 for _ in range(100001)]
MAX=100001

def bfs(x):
    dq=deque()
    dq.append(x)
    board[x] =1
    # 어떻게 끝내주지 ?
    # 흠. 
    while dq:
        x=dq.popleft()
        if 2*x<MAX and not board[2*x]:
            dq.appendleft(2*x)
            board[2*x]=board[x]
        if x+1<MAX and not board[x+1]:
            dq.append(x+1)
            board[x+1] = board[x]+1
        if 0<=x-1 and not board[x-1]:
            dq.append(x-1)
            board[x-1] = board[x]+1
bfs(N)
print(board[K]-1)