[백준] 13549 : 숨바꼭질 3 (Python)

정답코드

N, K = map(int, input().split())
visit = [-1]*100001
visit[N]=0

if N > K:
    print(N-K)
else:
    from collections import deque
    q = deque([N])
    while q:
        x = q.popleft()
        if x == K:
            print(visit[x])
            break
        if x < 50001 and visit[x*2] == -1:
            visit[x*2] = visit[x]
            q.appendleft(x*2)
        if 0 < x and visit[x-1] == -1:
            visit[x-1] = visit[x]+1
            q.append(x-1)
        if x < 100000 and visit[x+1] == -1:
            visit[x+1] = visit[x]+1
            q.append(x+1)

풀이

1. 해당 숫자를 몇 번 만에 만들었는지를 저장하기 위한 1차원 배열 visit 생성.
   방문하지 않은 곳은 -1, visit[N]=0으로 초기화
2. N이 K보다 큰 경우, -1을 반복하여 K가 되는 방법밖에 없으므로 가장 빠른 시간은 N-K이다.
   그 외의 경우는 else문으로.
3. N을 저장한 queue 생성
4. 방문할 수 있고 방문하지 않은 곳은 업데이트 visit에 시간을 업데이트 해가며 q에 append
   이 때, 순간이동(2*x)는 시간이 걸리지 않으므로 q에서 먼저 나오도록 appendleft한다.
5. K에 도달하면 프린트하고 while문 정지

반례모음

10000 0
10000

2 7
1

1 17
1

4 6
1

0 1
1

0 3
2

0 0
0

1 32
0

3 22
1

5 7
2

1 10000
3

1 100000
5