[BOJ] 백준 1697. 숨바꼭질 - BFS

🥈 숨바꼭질

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

💡 아이디어

BFS라는 것을 알고 풀어서 접근은 간단했다!

1. 시작점을 큐에 넣어주기
2. 큐에 있는 숫자 개수 만큼 탐색하기
3. 각각의 숫자를 +1, -1, *2로 계산하여 범위가 맞으면 큐에 넣어주기

🖊️ 풀이

# 숨바꼭질

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

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

q = deque()
q.append(n) # 시작점을 큐에 넣어준다

visited = [False] * (200001)
visited[n] = True # 시작점은 방문처리
cnt = 0
while q:
    for _ in range(len(q)):     
        x = q.popleft()
        if x == k:
            print(cnt)
            sys.exit(0)
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= 200000 and not visited[nx]:
                visited[nx] = True
                q.append(nx)
    cnt += 1

1. 방문할 숫자의 범위
2. 숫자를 찾으면 sys.exit(0)으로 프로그램을 종료하는 것

위 두 사항을 해결하느라 시간이 좀 걸렸다.