[백준 알고리즘] 1679. 숨바꼭질

 

 

 

 

 

 

처음엔 DFS로 접근할 수 있을 것 같아 DFS로 풀었는데, 시간이 너무 오래걸려 시간초과가 떴다.

 

최단거리엔 역시 BFS이구나를 깨닫고 다 지우고 BFS로 접근했다.

 

 

아래처럼 범위를 설정하지 않으면 visited때문에 런타임에러가 뜬다.

" if num > 100000 or 0 > num: continue " 

 

 

 

 

from collections import deque

def BFS(n):
    cnt = 0
    Q.append(n)
    while Q:
        for _ in range(len(Q)):
            num = Q.popleft()
            if num == k:
                return cnt
            if num > 100000 or 0 > num: continue
            if visited[num] == 1: continue
            visited[num] = 1

            if num > k :
                Q.append(num - 1)
            else:
                Q.append(num + 1)
                Q.append(num - 1)
                Q.append(num * 2)
        cnt += 1


n, k = map(int, input().split())
Q = deque()
visited = [0] * 100001
print(BFS(n))