[백준] 12851번: 숨바꼭질2 - python

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

12851번: 숨바꼭질 2

 

아이디어

 

체크할 필요가 없으니 체크리스트를 제거한 뒤에 거리가 같을 경우 cnt 값을 증가시키며 답을 출력

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

n, m = map(int, input().split())

ch = [0] * 100001
dis = [0] * 100001
cnt = 0
tmp = 0
ch[n] = 1
dq = deque([n])
answer = -1
while dq:
    now = dq.popleft()
    if now == m:
        cnt+=1
        answer = dis[m]
        continue

            
    for next in (now+1, now-1, now*2):
        if 0<=next<100001 and (dis[next] == 0 or dis[next] == dis[now]+1):
            if ch[next] == 0:
                dis[next] = dis[now] + 1
                dq.append(next)

print(answer)
print(cnt)

 

완성