좌표 평면 위에 시작점 (sx, sy)와 목표점 (tx, ty)가 주어졌다고 가정해 봅시다. 이때 시작점에서 출발하여 일련의 이동을 거쳐 목표점에 도달할 수 있는지 확인하는 것이 이 문제의 핵심입니다.
문제 정의
여기서 말하는 '이동(move)'은 현재 점 (x, y)를 다음 두 가지 방식 중 하나로 변환하는 것을 의미합니다.
- (x, y) → (x, x + y)
- (x, y) → (x + y, y)
예를 들어 입력이 시작점 (1, 1), 목표점 (4, 5)라면 정답은 true입니다. 다음 순서로 이동하면 목표점에 도달할 수 있기 때문입니다.
(1, 1) → (2, 1) → (3, 1) → (4, 1) → (4, 5)
접근 방법: 역방향 추적과 나머지 연산
목표점에서 시작점으로 거꾸로 거슬러 올라가는 방식으로 문제를 해결할 수 있습니다. 매번 큰 값을 작은 값으로 빼는 대신 나머지 연산(mod)을 활용하면 유클리드 호제법처럼 반복 횟수를 크게 줄일 수 있습니다.
구체적인 단계는 다음과 같습니다.
- tx > sx 이고 ty > sy 인 동안 다음을 반복합니다.
- tx > ty 라면 tx := tx mod ty
- 그렇지 않다면 ty := ty mod tx
- 반복이 끝난 후 아래 조건 중 하나라도 만족하면 true를 반환합니다.
- sx == tx 이고 sy <= ty 이며 (ty − sy) mod tx == 0 인 경우
- sy == ty 이고 tx >= sx 이며 (tx − sx) mod ty == 0 인 경우
이 조건의 의미는, 역방향 추적이 끝난 시점에 한 좌표가 이미 시작점과 일치하고, 나머지 좌표의 차이가 고정된 값의 배수라면 앞으로의 이동으로 정확히 맞출 수 있다는 것입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while(tx > sx && ty > sy){
if(tx > ty){
tx %= ty;
}else ty %= tx;
}
return (sx == tx && sy <= ty && (ty - sy) % tx == 0) || (sy == ty && tx >= sx && (tx - sx) % ty == 0);
}
};
main(){
Solution ob;
cout << (ob.reachingPoints(1,1,4,5));
}입력
1 1 4 5
출력
1
출력값 1은 불리언 true를 의미하며, 즉 (1, 1)에서 (4, 5)까지 도달하는 이동 경로가 존재한다는 뜻입니다.
정리
이 문제는 순방향으로 모든 경우를 탐색하면 비효율적이지만, 목표점에서 시작점 방향으로 나머지 연산을 활용해 거꾸로 추적하면 O(log n) 수준의 빠른 시간 안에 답을 구할 수 있습니다. 유클리드 호제법과 유사한 발상을 응용한 좋은 알고리즘 학습 예제입니다.