[백준] 1697 | 숨바꼭질 [파이썬/python]

문제

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

수빈이가 동생을 찾는 데 걸리는 시간을 구하는 문제이다.

수빈이의 위치가 X일 때, X-1, X+1, X*2로 이동할 수 있으며 한 번 이동할 때마다 1초가 걸린다.

 

접근

수빈이의 위치 N과 동생의 위치 K가 주어지는데, K가 N보다 작을 수도 있음을 꼭 고려해야 한다!

처음에는 DP로 풀까 했는데 코드가 복잡해지는 것 같아서(실력부족 때문일 수도 있다😅) BFS를 응용한 코드로 바꾸었다.

 

코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
v = [0 for _ in range(K*2+1 if K > N else N*2+1)]

tmp = set()
tmp.add(N)
cnt = 0

while tmp:
    tmp2, tmp= tmp, set()
    if K in tmp2:
        print(cnt)
        break
    cnt += 1
    for i in tmp2:
        v[i] = 1 
        for j in [i-1, i+1, i*2]:
            if 0 <= j < len(v) and not v[j]:
                tmp.add(j)