BOJ 1697 - 숨바꼭질

풀이

---

1차원 배열에서의 BFS 문제이다.

시작점 n 에서 k 에 도달할 때 까지 n 이 [n+1, n-1, n*2] 총 세가지 방식으로 n 을 움직일 수 있다.

이 모든 경우를 큐에 담은 뒤 방문한 지점마다 방문처리를 한다.

BFS 가 수행되면서 k 지점에 도달했을 경우, BFS 를 종료한 뒤 저장해뒀던 방문처리 - 1 의 값을 반환한다.

처음엔 코드가 수도없이 틀리길래 대체 뭐가 문제인가 싶어 한참을 고민했었는데 범위 계산에 오타가 있었음을 알았다.

항상 오타를 잘 확인해야겠다.

소스코드

---

# 숨바꼭질
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(n):
    q = deque()
    q.append(n)
    visited[n] = 1
    while q:
        x = q.popleft()
 
        if x == k:  # 목표점에 도달했을 경우
            return visited[x] - 1
 
        dx = [x+1, x-1, x*2]
        for nx in dx:
            if 0 <= nx < 100001 and visited[nx] == 0:  # 범위 내 이면서 방문하지 않았을 경우
                visited[nx] = visited[x] + 1  # 방문 처리 겸 초 계산
                q.append(nx)
 
 
visited = [0] * 100001
n, k = map(int, input().split())
 
print(bfs(n))

References

---

• BOJ 1697 - 숨바꼭질