풀이
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))