boj.kr/13549 숨바꼭질 3 (gold5) 파이썬 풀이

방문체크 배열에 소요시간 정보를 저장하는 방식으로 bfs 구현해 풀이한 결과 성공했다.

 

주의 : 방문체크 배열 크기는 최대+1 이어야 인덱스 오류나지 않는다.

N, K = map(int, input().split())
from collections import deque
chk = [-1] * 100_001
chk[N] = 0
def bfs():
    dq = deque()
    dq.append(N)
    while dq:
        cur = dq.popleft()
        if chk[K] != -1:
            return chk[K]
        if 0 <= cur*2 <= 100_000 and chk[cur*2] == -1:
            dq.appendleft(cur*2)
            chk[cur*2] = chk[cur]
        if 0 <= cur-1 <= 100_000 and chk[cur-1] == -1:
            dq.append(cur-1)
            chk[cur-1] = chk[cur] + 1
        if 0 <= cur+1 <= 100_000 and chk[cur+1] == -1:
            dq.append(cur+1)
            chk[cur+1] = chk[cur] + 1
print(bfs())

 

동일한 로직으로 while문 안에 for문을 사용하면 시간초과 발생한다