어떤 시작 위치 p에서 출발해 왼쪽 또는 오른쪽으로 d1 또는 d2 단위씩 자유롭게 점프할 수 있다고 가정해 보겠습니다. 이때 목표 위치 q까지 도달하는 데 필요한 최소 점프 횟수를 구하는 것이 이 글의 핵심 과제입니다.
예를 들어 입력이 p = 5, q = 10, d1 = 4, d2 = 3이라면 정답은 3입니다. 오른쪽으로 4단위씩 두 번 점프해 위치 13에 먼저 도달한 뒤, 왼쪽으로 3단위 점프하면 정확히 10에 도착할 수 있기 때문입니다.
문제 해결 접근 방식
이 문제는 최대공약수(GCD)를 이용한 도달 가능성 판별과 너비 우선 탐색(BFS)을 결합하면 깔끔하게 해결할 수 있습니다.
1단계: GCD로 도달 가능 여부 판별
d1과 d2를 조합해 만들 수 있는 모든 이동 거리는 d1과 d2의 최대공약수의 배수 형태가 됩니다(베주 항등원). 따라서 (p − q)가 gcd(d1, d2)로 나누어떨어지지 않으면 어떤 순서로 점프하더라도 q에 도달하는 것은 불가능하며, 즉시 -1을 반환하면 됩니다. 이 사전 검사를 통해 불필요한 탐색을 크게 줄일 수 있습니다.
2단계: BFS로 최소 점프 횟수 탐색
도달 가능성이 확인되면 BFS를 사용해 최소 점프 횟수를 찾습니다. BFS는 같은 거리에 있는 위치들을 단계별로 확장해 나가기 때문에, 목표 지점에 처음 도달하는 순간의 단계 수가 곧 최솟값이 됩니다. 이미 방문한 위치는 다시 큐에 넣지 않음으로써 무한 루프와 중복 탐색을 방지합니다.
알고리즘 단계
gcd_res:= d1과 d2의 최대공약수 계산- (p − q)가
gcd_res로 나누어떨어지지 않으면 -1 반환 - 덱(deque) 하나와 방문 기록용 집합(set)을 생성
- (p, 0) 쌍을 큐에 삽입하고 p를 방문 처리
- 큐가 빌 때까지 다음을 반복:
- 큐에서 (현재 위치, 현재 단계)를 꺼냄
- 현재 위치가 q와 같으면 현재 단계 반환
- 현재 위치에서 +d1, +d2, −d1, −d2로 이동한 네 위치 중 아직 방문하지 않은 곳을 큐에 삽입하고 방문 처리
파이썬 구현 예시
from math import gcd
from collections import deque
def solve(p, d1, d2, q):
# 도달 가능성 검사: 차이가 gcd의 배수가 아니면 실패
gcd_res = gcd(d1, d2)
if (p - q) % gcd_res != 0:
return -1
que = deque()
visited = set()
que.appendleft([p, 0])
visited.add(p)
while len(que) > 0:
pair = que.pop()
point, step = pair[0], pair[1]
if point == q:
return step
if point + d1 not in visited:
que.appendleft([(point + d1), step + 1])
visited.add(point + d1)
if point + d2 not in visited:
que.appendleft([(point + d2), step + 1])
visited.add(point + d2)
if point - d1 not in visited:
que.appendleft([(point - d1), step + 1])
visited.add(point - d1)
if point - d2 not in visited:
que.appendleft([(point - d2), step + 1])
visited.add(point - d2)
p = 5
q = 10
d1 = 4
d2 = 3
print(solve(p, d1, d2, q))실행 결과
입력:
5, 4, 3, 10
출력:
3
복잡도 분석
BFS가 탐색하는 상태 공간은 점프 거리 조합에 따라 확장되지만, 방문 집합 덕분에 각 위치는 최대 한 번만 처리됩니다. 따라서 시간 복잡도와 공간 복잡도는 모두 유효 탐색 범위에 비례하는 O(N) 수준입니다.
마무리
GCD 검사로 불가능한 경우를 조기에 걸러내고, BFS로 최단 경로를 보장하는 이 조합은 그래프 탐색 문제에서 자주 쓰이는 강력한 패턴입니다. 점프 게임, 로봇 이동 시뮬레이션 등 유사한 최소 이동 횟수 문제에도 그대로 응용할 수 있으니 꼭 기억해 두세요.