백준 12851 파이썬 python : 숨바꼭질 2 @@황소처럼 우직하게@@ 어여와 반례들 있응께

5 1000

입력했을 때,

11

2

가 나오는가?

안나온다면 중복을 해결하지 못한것이여.

그리고

n == k 일 때,

0

1

이 나와야혀.

코드는 다음과 같네

dp2 로 중복 개수를 헤아렷네.

n, k = map(int, input().split())
if n == k:
    print(0)
    print(1)
    exit()

dp = [-1] * 150001
dp2 = [1] * 150001

flag = False
dist = -1
count = 0
dp[n] = 0
q = [n]
q2 = []
while q:
    now = q.pop(0)
    if now + 1 <= 150000:
        if dp[now + 1] == dp[now] + 1:
            dp2[now + 1] += dp2[now]
        elif dp[now + 1] == -1:
            if now + 1 == k:
                flag = True
                count += dp2[now]
            else:
                dp[now + 1] = dp[now] + 1
                dp2[now + 1] = dp2[now]
                q2.append(now + 1)
    if now - 1 >= 0:
        if dp[now - 1] == dp[now] + 1:
            dp2[now - 1] += dp2[now]
        elif dp[now - 1] == -1:
            if now - 1 == k:
                flag = True
                count += dp2[now]
            else:
                dp[now - 1] = dp[now] + 1
                dp2[now - 1] = dp2[now]
                q2.append(now - 1)
    if now * 2 <= 150000:
        if dp[now * 2] == dp[now] + 1:
            dp2[now * 2] += dp2[now]
        elif dp[now * 2] == -1:
            if now * 2 == k:
                flag = True
                count += dp2[now]
            else:
                dp[now * 2] = dp[now] + 1
                dp2[now * 2] = dp2[now]
                q2.append(now * 2)
    if not q and not flag:
        q = q2
        q2 = []

print(dp[now] + 1)
print(count)