백준 13549 파이썬

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

13549번: 숨바꼭질 3

 

수빈이는 움직이고, 동생은 움직이지 않는다. 따라서 수빈이가 움직이는 경우만 잘 처리해주면 된다.

 

기본적인 BFS 문제인데, 하나 조심해야할 부분은 순간이동을 하게 되면 이동하는데 필요한 시간이 0초라는 것이다. 따라서 순간이동하는 경우도 가장 뒷쪽으로 넣은 경우, 수빈이가 동생을 만나는 모든 경우의 수에 대해 최소값을 기록해야 정답이 된다.

 

반대로 Deque을 사용한다면, 순간이동을 하는 경우는 시간의 증가가 없기 때문에 가장 앞으로 보내주면 항상 가장 빠른 시간이 된다. 따라서 이 때는 최소값을 체크할 필요없이 수빈이와 동생이 만나는 순간 답을 출력하고 종료하면 된다.

 

import sys
from collections import deque

def sol(n,k):
    que = deque()
    que.append((n,0))
    v[n] = 0

    while que :
        now_posi, time = que.popleft()

        if now_posi == k :
            print(time)
            return

        next_time = time + 1

        if now_posi + 1 <= 100000 and v[now_posi + 1] > next_time :
            v[now_posi + 1] = next_time
            que.append((now_posi + 1 , next_time))

        if now_posi - 1 >= 0 and v[now_posi -1] > next_time :
            v[now_posi - 1] = next_time
            que.append((now_posi -1 , next_time))

        if now_posi * 2  <= 100000 and v[now_posi * 2 ] > time :
            v[now_posi * 2 ] = time
            que.appendleft((now_posi * 2  , time))


n,k = map(int,sys.stdin.readline().split())
v = [9876543210 for _ in range(100000 + 1 )]

sol(n,k)