1697번 파이썬

bfs를 이용한 문제

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

n, k = map(int, input().split())
queue = deque([n])
count = [0]*100001
while queue:
    roc = queue.popleft()
    if roc == k:
        print(count[k])
        break
    if 0<=(2*roc) <= 100000 and count[2*roc] ==0:
        count[2*roc] = count[roc]+1
        queue.append(2*roc)
    if 0 <= (roc-1)<=100000 and count[roc-1] ==0:
        count[roc-1] = count[roc]+1
        queue.append(roc-1)
    if 0<=(roc+1) <= 100000 and count[roc+1] ==0:
        count[roc+1] = count[roc]+1
        queue.append(roc+1)

처음엔 위에 방법으로 접근해봤는데 이상하게 자꾸 채점하다가 틀렸다는 문구가 뜬다,,

아래 코드는 다른 사람이 푼걸 참고한건데 아무리 비교해봐도 코드가 조금 길어졌을뿐 결과값이 왜 달라지는지 모르겠다.. roc-1이나 2*roc이나 roc+1이 0이나 100000 둘중 하나를 초과하는 경우가 있는 것 같은데 정확히는 잘 모르겠다,,

not count[idx] 문법이 count[idx]=0인걸 찾기 위해서인것 같은데 오타난 곳은 없고 무슨 에러인지는 잘모르겠다

어쨋든 풀이 방법은 2배를 뛰어넘거나 +-1인 경우가 아직 지나가지 않은 경로(값이 0)라면 이 전에 있던 경로에 1을 추가해준다 ex) count[2*roc]=count[roc]+1

계속 그렇게 bfs 방법을 반복하다보면 count[k]에도 값이 들어가게 되고 roc == k와 같아질때 count[k]값을 출력해준다.

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

n, k = map(int, input().split())
queue = deque([n])
count = [0]*100001
while queue:
    roc = queue.popleft()
    if roc == k:
        print(count[k])
        break
    for idx in (roc-1,roc+1,2*roc):
        if 0<=idx<=100000 and not count[idx]:
            count[idx]=count[roc]+1
            queue.append(idx)