[백준 12851번] 숨바꼭질 2 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
INF = sys.maxsize

N,K = map(int,input().split())

if N >= K:
  print(N-K)
  print(1)
else:
  DP = [INF]*2*K
  count = [0]*2*K
  DP[N] = 0
  count[N] = 1
  
  dq = deque()
  dq.append(N)
  
  while dq:
    x = dq.popleft()
    if 2*x < 2*K:
      if DP[2*x] > DP[x]+1:
        DP[2*x] = DP[x]+1
        count[2*x] = 1
        dq.append(2*x)
      elif DP[2*x] == DP[x]+1:
        count[2*x] += 1
        dq.append(2*x)
    if x+1 < 2*K:
      if DP[x+1] > DP[x]+1:
        DP[x+1] = DP[x]+1
        count[x+1] = 1
        dq.append(x+1)
      elif DP[x+1] == DP[x]+1:
        count[x+1] += 1      
        dq.append(x+1)
    if x > 0:
      if DP[x-1] > DP[x]+1:
        DP[x-1] = DP[x]+1
        count[x-1] = 1
        dq.append(x-1)
      elif DP[x-1] == DP[x]+1:
        count[x-1] += 1
        dq.append(x-1)
  print(DP[K])
  print(count[K])

 

이전의 숨바꼭질1을 변형한 문제이다. 거의 다 풀어놓고 이상한데서 생각이 꼬여서 해메고 있었는데, DP가 변하면 count를 1로 바꾸는게 아니라 이전 count값으로 바꿔주고 있었다... 이를테면 count[2*x] = count[x] 이런식으로

 

생각은 이전 경우의 수를 그대로 받는다는 의미였는데, 어차피 dp에 중복해서 들어가기 때문에 카운트가 오히려 중복해서 되어버린..

 

 

오늘의 교훈) 알고리즘을 천천히 따라가면서 오류를 잡아내자