[백준] 1697 숨바꼭질(python)

✅문제

✏️풀이

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

MAX_POSITION = 100000

visit = [0] * (MAX_POSITION + 1)

def bfs():
    queue = []  # 리스트를 큐로 사용
    queue.append(n)
    while queue:
        x = queue.pop(0)
        if x == k:
            print(visit[x])
            break
        for j in (x-1, x+1, x*2):
            if 0 <= j <= MAX_POSITION and not visit[j]:  
                visit[j] = visit[x] + 1  # 이동 횟수 갱신
                queue.append(j) 


bfs()

📌체크

BFS(너비 우선 탐색)

큐를 사용하여 탐색해야 할 노드를 순차적으로 처리

deque(double-ended queue)

: 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 양방향 큐를 의미

• 파이썬의 collections 모듈에 포함
• 리스트와 비슷하지만 양쪽 끝에서의 삽입과 삭제가 매우 빠른 자료구조

⭕정답확인